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.")

Explicație

Programul primește ca date de intrare un număr și o listă de numere, apoi calculează numărul de perechi de elemente din listă care au cel mai mic multiplu comun (CMMMC) egal cu numărul dat.

Validarea datelor de intrare este realizată prin funcția validare_date(), care verifică dacă numărul dat și toate numerele din lista se încadrează într-un anumit interval.

Funcția numar_perechi_cu_cmmmc_x(x) primește un număr x și calculează numărul de perechi de numere întregi pozitive din intervalul [1, x] a căror CMMMC este egal cu x. Acest calcul se face prin descompunerea numărului x în factori primi, iar apoi se calculează puterea fiecărui factor în CMMMC. În final, se folosește formula matematică a lui Euler pentru a calcula numărul de perechi de numere cu CMMMC x.

În funcție de validarea datelor de intrare, se afișează pentru fiecare număr din listă numărul de perechi de numere cu CMMMC egal cu numărul dat sau un mesaj corespunzător.