Masala #XJHOELPHJX
MAX GCD
Sizga n ta butun sondan iborat to'plam berilgan. Bu to'plamda bir xil sonlar takrorlanishi mumkin. Sizning vazifangiz bu to'plamni k ta ajratilgan guruhlarga bo'lish va har bir guruh uchun o'sha guruhdagi sonlarning eng katta umumiy bo'luvchisini (GCD) hisoblash. Keyin barcha guruhlarning GCD larini yig'indisini hisoblang.
Sizdan so'ralgan vazifa: har bir k=1, 2, …, n uchun, to'plamni k ta guruhga bo'lish orqali olinadigan maksimal GCD yig'indisini topish.
Kiruvchi ma'lumotlar:
Birinchi qatorda bitta butun son n (to'plamdagi elementlar soni) beriladi. \((1≤n≤5*10^5)\)
Ikkinchi qatorda n ta musbat butun son (to'plam elementlari) beriladi. \((1≤a_i≤10^{12})\)
Chiquvchi ma'lumotlar:
n ta qator har birida bitta butun son bo'lishi kerak:
- Birinchi qatorda k=1 uchun maksimal GCD yig'indisi.
- Ikkinchi qatorda k=2 uchun maksimal GCD yig'indisi.
- .……………………………………………………………………………………….
- n-chi qatorda k=n uchun maksimal GCD yig'indisi.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 10 9 10 3 |
1 13 23 32 |
| 2 |
8 15 25 29 30 43 44 45 55 |
1 56 101 145 188 221 256 286 |
Izoh:
1-testdsa.
- k=1 uchun barcha sonlar bitta guruhda. GCD(10, 9, 10, 3) = 1. Yig'indi: 1.
- k=2 uchun eng yaxshi bo'linish: (10,10) va (9,3). GCD(10, 10) = 10, GCD(9, 3) = 3. Yig'indi: 10 + 3 = 13.
- k=3 uchun eng yaxshi bo'linish: (10), (10) va (9,3). GCD(10) = 10, GCD(10) = 10, GCD(9, 3) = 3. Yig'indi: 10 + 10 + 3 = 23.
- k=4 uchun har bir son alohida guruhda. GCD(10) = 10, GCD(9) = 9, GCD(10) = 10, GCD(3) = 3. Yig'indi: 10 + 9 + 10 + 3 = 32.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling