3311 - Nr Reg

Enunt

Numerele regulate sunt numerele ce au ca factori primi doar numerele 2, 3 și 5. Primele 20 de numere regulate sunt: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36.

Cerinta

Fișierul de intrare nrregin.txt conține pe prima linie numărul natural n (n<=10000). Scrieți un program care determină:

• cel de-al n-lea număr regulat, x;
• cel mai mic divizor d al lui x cu proprietatea că p = x / d este pătrat perfect;
• valoarea p.

Programul va scrie în fișierul nrregout.txt valorile x d p, separate prin câte spațiu.

Exemplu: dacă n=10, al zecelea număr regulat este x=12; d=3, iar p=4.

Date de intrare

Fișierul de intrare nrregin.txt conține pe prima linie numărul natural n.

Date de iesire

Fișierul de ieșire nrregout.txt va conține pe prima linie numărul x d p, separate prin câte un spațiu.

Restrictii si precizari

• 1 ⩽ n ⩽ 10000
• prin convenție s-a stabilit că numărul 1 face parte din șirul numerelor regulate.

Exemplul 1

nrregin.txt

10

nrregout.txt

Datele introduse corespund restrictiilor impuse

12 3 4

Exemplul 2

nrrgin.txt

17

Datele introduse nu corespund restrictiilor impuse

Rezolvare

def cel_mai_mic_divizor_patratic(n):
    numere_regulate = [1]
    while len(numere_regulate) < n:
        for x in numere_regulate:
            for d in [2, 3, 5]:
                if x * d not in numere_regulate:
                    numere_regulate.append(x * d)
        numere_regulate.sort()

    x = numere_regulate[n - 1]

    # Determinăm cel mai mic divizor pătratic
    d = 2
    while x % (d ** 2) != 0:
        d += 1

    p = x // (d ** 2)
    return x, d, p

def verificare_rezultat(x, d, p):
    # Adăugăm condițiile de verificare
    return x % (d ** 2) == 0 and all(x % (f ** 2) == 0 for f in [2, 3, 5])

# Citire date de intrare
with open("nrregin.txt", "r") as file:
    n = int(file.readline())

# Calcul și afișare rezultat
rezultat = cel_mai_mic_divizor_patratic(n)

# Verificare rezultat
if verificare_rezultat(*rezultat):
    with open("nrregout.txt", "w") as file:
        file.write(" ".join(map(str, rezultat)) + "\n")
else:
    print("Rezultat invalid. Verificați condițiile.")

Explicatie

Al zecelea număr regulat este 12; numărul minim care îl divide pe 12 pentru a obține un pătrat perfect este 3 iar pătratul perfect este 4.