2141 - Exp

Enunț

Se dă un şir de n numere naturale nenule x1, x2, …, xn şi un număr natural m.

Cerința

Să se verifice dacă valoarea expresiei radical de ordin m din (x1⋅x2⋅…⋅xn) este un număr natural. În caz afirmativ să se afișeze acest număr descompus în factori primi.

Date de intrare

Fișierul de intrare expIN.txt conține pe prima linie m, pe linia a doua n, iar pe linia a treia numerele x1, x2, …, xn separate între ele prin câte un spațiu.

Date de ieșire

În fișierul de ieșire expOUt.txt se va scrie pe prima linie cifra 0, dacă valoarea expresiei nu este un număr natural, respectiv 1 dacă este un număr natural. Dacă valoarea expresiei este un număr natural pe următoarele linii se vor scrie perechi de forma p e (p este factor prim care apare în descompunere la puterea e>=1). Aceste perechi se vor scrie în ordine crescătoare după primul număr (adică p).

Restricții și precizări

• 0 < n < 5000
• 0 < xi < 30.001, pentru orice i=1..n
• m poate fi una din cifrele 2, 3, 4.

Exemplul 1:

expIN.txt

2
4
32 81 100 18

expOUt.txt

1
2 4
3 3
5 1

Exemplul 2:

expIN.txt

6
6
45 5 44 23 32 32

consola:

Eroare: Numărul m trebuie să fie una din cifrele 2, 3, 4.

Rezolvare

def respecta_restrictiile(m, n, xi):
    if not (0 < n < 5000):
        print("Eroare: Numărul de elemente n trebuie să fie între 0 și 5000.")
        return False

    if not (0 < m < 5):
        print("Eroare: Numărul m trebuie să fie una din cifrele 2, 3, 4.")
        return False

    if not all(0 < x < 30001 for x in xi):
        print("Eroare: Elementele xi trebuie să fie în intervalul (0, 30001).")
        return False

    return True

def este_numar_natural(n):
    return n == int(n) and n > 0

def descompunere_in_factori_primi(numar):
    factori_primi = []
    divizor = 2
    
    while divizor <= numar:
        putere = 0
        while numar % divizor == 0:
            numar //= divizor
            putere += 1
        if putere > 0:
            factori_primi.append((divizor, putere))
        divizor += 1
    
    return factori_primi

def main():
    with open("expIN.txt", "r") as f:
        m = int(f.readline().strip())
        n = int(f.readline().strip())
        xi = list(map(int, f.readline().split()))

    if not respecta_restrictiile(m, n, xi):
        return

    # Restul codului pentru calcule și scrierea în fișier rămâne neschimbat
    produs = 1
    for x in xi:
        produs *= x

    radical_m = produs ** (1/m)

    with open("expOUT.txt", "w") as f:
        if este_numar_natural(radical_m):
            f.write("1\n")
            factori_primi = descompunere_in_factori_primi(int(radical_m))
            for factor, putere in factori_primi:
                f.write(f"{factor} {putere}\n")
        else:
            f.write("0\n")

if __name__ == "__main__":
    main()