3203 - SimonaH: Diferență între versiuni
De la Universitas MediaWiki
Linia 32: | Linia 32: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <syntaxhighlight lang="python3" line="1"> | ||
def este_input_valid(n, p): | |||
return 1 <= n <= 10**18 and 2 <= p <= 5 | |||
def putere_modulo(x, y, p): | def putere_modulo(x, y, p): | ||
result = 1 | result = 1 | ||
Linia 63: | Linia 66: | ||
return suma_totala | return suma_totala | ||
# Citire date de intrare | if __name__ == "__main__": | ||
# Citire date de intrare | |||
n, p = map(int, | n, p = map(int, input("Introduceți numerele n și p, separate prin spațiu: ").split()) | ||
# Calcul | # Verificare validitate date de intrare | ||
rezultat = suma_resturi_permutari(n) | if not este_input_valid(n, p): | ||
print("Datele introduse nu corespund restricțiilor impuse.") | |||
else: | |||
# Calcul și afișare rezultat în fișierul de ieșire | |||
rezultat = suma_resturi_permutari(n) | |||
with open("simonahout.txt", "w") as f: | |||
f.write(str(rezultat) + "\n") | |||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea curentă din 29 decembrie 2023 11:25
Cerinta
Din perfecţiunea Simonei H. a apărut şi noţiunea de p-număr, un număr natural cu cifre nenule, ale cărui cifre le putem permuta. Să se afle suma resturilor împărţirii tuturor numerelor obţinute prin permutarea cifrelor lui n la un număr dat p.
Date de intrare
Fișierul de intrare simonahin.txt conține pe prima linie numerele n şi p.
Date de iesire
Fișierul de ieșire simonahout.txt va conține pe prima linie suma resturilor împărţirii tuturor numerelor obţinute prin permutarea cifrelor lui n la numărul dat p.
Restrictii si precizari
- 1 ⩽ n ⩽ 10^18
- 2 ⩽ p ⩽ 5
Exemplul 1
- simonahin.txt
- 325 5
- simonahout.txt
- Datele introduse corespund restrictiilor impuse
- 10
Exemplul 2
- simonahin.txt
- 652 1
- Datele introduse nu corespund restrictiilor impuse
Rezolvare
def este_input_valid(n, p):
return 1 <= n <= 10**18 and 2 <= p <= 5
def putere_modulo(x, y, p):
result = 1
x = x % p
while y > 0:
if y % 2 == 1:
result = (result * x) % p
y = y // 2
x = (x * x) % p
return result
def suma_resturi_permutari(n):
suma_totala = 0
for p in [2, 3, 4, 5]:
cifre = [int(digit) for digit in str(n)]
factorial_inv = 1
cifre_freq = [0] * 10
for cifra in cifre:
cifre_freq[cifra] += 1
for i in range(1, 10):
factorial_inv = (factorial_inv * putere_modulo(i, cifre_freq[i], p)) % p
invers_mod_p = putere_modulo(factorial_inv, p-2, p)
suma_totala = (suma_totala + invers_mod_p) % p
return suma_totala
if __name__ == "__main__":
# Citire date de intrare
n, p = map(int, input("Introduceți numerele n și p, separate prin spațiu: ").split())
# Verificare validitate date de intrare
if not este_input_valid(n, p):
print("Datele introduse nu corespund restricțiilor impuse.")
else:
# Calcul și afișare rezultat în fișierul de ieșire
rezultat = suma_resturi_permutari(n)
with open("simonahout.txt", "w") as f:
f.write(str(rezultat) + "\n")
Explicatie
Numerele 325, 235, 532, 352, 253, 523 împărţite la 5 dau resturile 0,0,2,2,3,3, suma acestora fiind 10.