3055 - pericol

Enunt

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ța

Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.

Date de intrare

În fișierul text pericolIN.txt 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 pericolOUT.txt 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 și precizări

• 1 ≤ N ≤ 200.000
• 1 ≤ vk ≤ 10.000.000, 1 ≤ k ≤ N
• Pentru teste în valoare de 14 puncte N ≤ 2000
• Pentru alte teste în valoare de 5 puncte vk ≤ 2000
• Pentru alte teste în valoare de 39 de puncte vk ≤ 2.000.000

Exemplul 1:

pericolIN.txt

6
2 3 4 5 6 4

pericolOUT.txt

8 7 10 5 10 10

Explicație

De exemplu indicatorul de pericol al celui de-al cincilea elev se calculează astfel

(2,6) + (3,6) + (4,6) + (5,6) + (4,6) = 2+3+2+1+2 = 10

Exemplul 2:

pericolIN.txt

20000000000
2 3 4 5 6 4

pericolOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verifica_restrictiile(N, V):
    if not (2 <= N <= 200000 and all(1 <= v <= 10000000 for v in V)):
        with open("pericolOUT.txt", "w") as outfile:
            outfile.write("Datele nu corespund restrictiilor impuse\n")
        exit(1)

def main():
    with open("pericolIN.txt", "r") as infile, open("pericolOUT.txt", "w") as outfile:
        N = int(infile.readline().strip())
        V = list(map(int, infile.readline().split()))

        verifica_restrictiile(N, V)

        max_value = max(V) + 1

        count = [0] * max_value
        for x in V:
            count[x] += 1

        elementary = [True] * max_value
        primes = [0] * max_value
        formula = [0] * max_value
        answer = [0] * max_value

        primes[1] = 2

        for i in range(1, max_value):
            if primes[i] == 0:
                for j in range(i, max_value, i):
                    primes[j] += 1
                if i * i < max_value:
                    for j in range(i * i, max_value, i * i):
                        elementary[j] = False

            if elementary[i]:
                sign = 1 if primes[i] % 2 == 0 else -1
                for j in range(i, max_value, i):
                    formula[j] += sign * (j // i)

            frequency = sum(count[j] for j in range(i, max_value, i))

            for j in range(i, max_value, i):
                answer[j] += formula[i] * frequency

        result = [answer[x] - x for x in V]
        outfile.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":
    main()