2323 - Prim 001

Cerinţa

Se dă un număr natural n. Să se afle numărul divizorilor naturali ai lui n^n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieşire

Programul va afișa pe ecran numărul divizorilor lui n^n, modulo 59999.

Restricții și precizări

• 1 ≤ n ≤ 10^13

Exemplu

Intrare

4

Ieșire

9

Explicație

Numărul 4^4=256 are 9 divizori: 1,2,4,8,16,32,64,128,256.

Rezolvare

def valideaza_date(n):   
    if not n.isdigit() or int(n) <= 0:
        return False
    return True

if __name__ == '__main__':
    n = input("Introduceți un număr întreg pozitiv: ")
    if valideaza_date(n):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")      
        n = int(n)
        cnt, d = 1, 2
        cn = n
        while n > 1:
            p = 0
            while n % d == 0:
                n //= d
                p += 1
            cnt *= (p * cn + 1)
            d += 1
            if d * d > n:
                d = n
            while cnt >= 59999:
                cnt %= 59999
        print(cnt % 59999)
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")

Explicație rezolvare

Programul primește un număr întreg pozitiv de la utilizator și calculează numărul divizorilor acestuia folosind formula: numărul total de divizori ai lui n este produsul (p * cn + 1), unde p este exponentul unui factor prim, iar cn este numărul nesimplificat.

Pentru a calcula divizorii, programul parcurge toți factorii primi ai numărului și calculează exponenții lor. De asemenea, programul utilizează o condiție pentru a nu depăși pătratul numărului, care ar fi un factor mai mare decât numărul în sine.

În final, programul afișează numărul total de divizori al numărului, modulo 59999. De asemenea, acesta include o funcție valideaza_date() pentru a valida intrarea utilizatorului.