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

<syntaxhighlight lang="python" line>

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

</syntaxhighlight>

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.