2323 - Prim 001: Difference between revisions
Paul Matei (talk | contribs) Pagină nouă: == 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,25... |
Diana Butuza (talk | contribs) |
||
| Line 21: | Line 21: | ||
return False | return False | ||
return True | return True | ||
if __name__ == '__main__': | if __name__ == '__main__': | ||
n = input("Introduceți un număr întreg pozitiv: ") | n = input("Introduceți un număr întreg pozitiv: ") | ||
if valideaza_date(n): | if valideaza_date(n): | ||
print("\nDatele de intrare corespund restricțiilor impuse.\n") | print("\nDatele de intrare corespund restricțiilor impuse.\n") | ||
n = int(n) | n = int(n) | ||
cnt, d = 1, 2 | cnt, d = 1, 2 | ||
cn = n | cn = n | ||
while n > 1: | while n > 1: | ||
p = 0 | p = 0 | ||
| Line 44: | Line 40: | ||
while cnt >= 59999: | while cnt >= 59999: | ||
cnt %= 59999 | cnt %= 59999 | ||
print(cnt % 59999) | print(cnt % 59999) | ||
else: | else: | ||
print("Datele de intrare nu corespund restricțiilor impuse.") | print("Datele de intrare nu corespund restricțiilor impuse.") | ||
</syntaxhighlight> | |||
==Explicație rezolvare== | ==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. | 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. | ||
Revision as of 08:30, 6 April 2023
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.