Fişierul intrare/ieşire: | pericol.in, pericol.out | Sursă | ONI 2019, clasa a 10-a, ziua 2 |
Autor | Adrian Budau | Adăugată de | |
Timp execuţie pe test | 15 sec | Limită de memorie | 524288 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pericol
Avem o clasă cu N elevi inventivi. Pentru fiecare dintre ei se cunoaşte un coeficient de atitudine reprezentat printr-un număr natural nenul vk. Interacţiunile din cadrul grupului de elevi al clasei produc efecte secundare importante şi conducerea şcolii a definit o mărime scalară numită indicator de pericol care măsoară influenţa pe care un elev o are asupra celorlalţi elevi din clasă. Indicatorul de pericol asociat elevului k, 1 ≤ k ≤ N, se obţine calculând cel mai mare divizor comun dk, j pentru fiecare pereche (vk, vj), 1 ≤ j ≤ N, j ≠ k şi apoi însumând valorile calculate.
Cerinţă
Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.
Date de intrare
În fişierul text pericol.in pe prima linie se află numărul natural N. Pe a doua linie se află N numere naturale nenule, separate prin câte un spaţiu, reprezentând coeficienţii de atitudine ai celor N elevi.
Date de ieşire
În fişierul text pericol.out se vor scrie, pe prima linie, N numere naturale, separate prin câte un spaţiu, al k-lea număr natural reprezentând indicatorul de pericol asociat celui de-al k-lea elev.
Restricţii
- 1 ≤ N ≤ 2 * 105
- 1 ≤ vk ≤ 107, 1 ≤ k ≤ N
- Pentru teste în valoare de 14 puncte N ≤ 2.000
- Pentru alte teste în valoare de 5 puncte vk ≤ 2.000
- Pentru alte teste în valoare de 39 de puncte vk ≤ 2 * 106
Exemplu
pericol.in | pericol.out |
---|---|
6 2 3 4 5 6 4 | 8 7 10 5 10 10 |
Explicaţie
De exemplu, indicatorul de pericol al celui de-al 5-lea elev se calculează astfel:
(2, 6) + (3, 6) + (4, 6) + (5, 6) + (4, 6) = 2 + 3 + 2 + 1 + 2 = 10