TR-O4. Teng bo‘laklar

Bog‘dagi n ta daraxt ko‘chati yo‘lkalar bilan daraxt shaklida ulangan, i-ko‘chatda aᵢ ta meva bor. Bog‘ni bir nechta yo‘lkani kesib, sinflar o‘rtasida bo‘lib bermoqchi: har bir bo‘lak — bog‘langan qism, va har bir bo‘lakda mevalar soni bir xil bo‘lishi kerak.

Eng ko‘pi bilan nechta bo‘lakka bo‘lish mumkin?

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida a₁ … aₙ. Keyingi n − 1 qatorda yo‘lkalar u v.

Chiqish ma’lumotlari

Bitta son — bo‘laklarning eng ko‘p soni (hech narsa kesmasa — 1).

Cheklovlar

1 ≤ n ≤ 2·10⁵; 1 ≤ aᵢ ≤ 10.

1-misol: jami 6 ta meva. 2–3 va 1–4 yo‘lkalarini kessak, {1, 2}, {3}, {4} — har birida 2 ta: 3 bo‘lak. 6 ta bo‘lak (har birida 1 ta) bo‘lmaydi — qiymatlar 1 dan katta.