3486 - Factorul IX

Cerința

Numim factorul-x a 2 numere produsul tuturor factorilor primi comuni și diferiți ai celor 2 numere.

Se dau n numere naturale distincte. Se cere să se afle câți factori-x diferiți pot fi obținuți din toate perechile diferite de numere din șir și să se afișeze aceștia.

Date de intrare

Fișierul de intrare factorulx.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte separate prin spații.

Date de ieșire

Fișierul de ieșire factorulx.out va conține pe prima linie numărul de factori-x diferiți care pot fi obținuți din toate perechile diferite de numere din șir, iar pe a 2-a linie toți aceștia, afișați în ordine crescătoare și separați prin câte un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 1000
• numerele de pe a doua linie a fișierului de intrare vor fi distincte și mai mici decât 2.000.000.000
• dacă 2 numere nu au niciun factor prim comun, atunci, prin convenție se alege ca factorul-x al celor 2 numere să fie 1
• punctajul pe test va fi acordat doar dacă ambele numere afișate sunt corecte.

Exemplu:

factorulx.in

9
2 4 6 7 9 15 18 20 21

factorulx.out

6
1 2 3 5 6 7

Explicatie:

Factorul-x pentru 15 și 18 este 3(3 este singurul lor factor prim comun), pentru 7 și 21 este 7 (la fel ca în cazul anterior), pentru 6 și 18 este 6(2 * 3), pentru 2 și 7 este 1 etc.

Încărcare soluție

import math

f = open("factorulx.in", "r")
g = open("factorulx.out", "w")

def factorx(n):
    P = 1
    if n % 2 == 0:
        P *= 2
        while n % 2 == 0:
            n >>= 1
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            P *= i
            while n % i == 0:
                n = n // i
    if n > 2:
        P *= n
    return P

n = int(f.readline())
v = [0] * 1024
fact = [0] * 524288

i = 0
j = 0
m = 0
k = 0
P = 0

for i in range(1, n + 1):
    v[i] = int(f.readline())

for i in range(1, n):
    for j in range(i + 1, n + 1):
        m = math.gcd(v[i], v[j])
        P = factorx(m)
        if P not in fact[1:k + 1]:
            k += 1
            fact[k] = P
            fact[1:k + 1].sort()

g.write(str(k) + '\n')
fact[1:k + 1].sort()
for i in range(1, k + 1):
    g.write(str(fact[i]) + " ")

f.close()
g.close()