3203 - SimonaH

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

<syntaxhighlight lang="python3" line="1"> 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

1. Citire date de intrare

with open("simonahin.txt", "r") as f:

   n, p = map(int, f.readline().split())

1. Calcul suma resturilor

rezultat = suma_resturi_permutari(n)

1. Scriere rezultat în fișierul de ieșire

with open("simonahout.txt", "w") as f:

   f.write(str(rezultat) + "\n")

</syntaxhighlight>

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.