0664 - Nr Perechi

Cerinţa

Gigel a învăţat la matematică despre cel mai mic multiplu comun a două numere şi acum trebuie să determine pentru fiecare valoare x dintr-un set de valori date câte perechi ordonate de numere naturale (a,b) au cel mai mic multiplu comun x.

Date de intrare

Programul citește de la tastatură număr numar, apoi numere valori x.

Date de ieşire

Programul va afișa pe ecran n valori, separate prin exact un spaţiu; fiecare valoare afișată reprezintă numărul de perechi care au cel mai mic multiplu comun egal cu valoarea x corespunzătoare.

Restricții și precizări

• numar ∈ Ν
• 1 ⩽ numar ⩽ 1.000
• 1 ⩽ x ⩽ 2.000.000.000

Exemplu

Intrare

2

12 4

Ieșire

Datele de intrare corespund restricțiilor impuse.

15 5

Explicație

Cele 15 perechi pentru care cel mai mic multiplu comun este 12 sunt: (1,12), (2,12), (3,4), (3,12), (4,3), (4,6), (4,12), (6,4), (6,12), (12,1), (12,2), (12,3), (12,4), (12,6), (12,12).

Rezolvare

def validare_date(numar, numere):
    flag = False
    if 0 <= int(numar) <= 1_000:
        flag = all(isinstance(x, int) and 1 <= x <= 1_000_000 for x in numere)
    return flag


def numar_perechi_cu_cmmmc_x(x):
    divizor = 2
    putere_divizor = 1
    while x > 1:
        if x % divizor == 0:
            exponent_divizor = 0
            while x % divizor == 0:
                exponent_divizor += 1
                x //= divizor
            putere_divizor *= 2 * exponent_divizor + 1
        else:
            divizor += 1
        if x > 1 and divizor * divizor > x:
            putere_divizor *= 3
            break
    return putere_divizor


if __name__ == '__main__':
    numar = int(input())
    numere = list(map(int, input().split()))
    if validare_date(numar, numere):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
        for x in numere:
            print(numar_perechi_cu_cmmmc_x(x), end=' ')
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")