3203 - SimonaH: Difference between revisions

Latest revision as of 11:25, 29 December 2023

Cerinta[edit | edit source]

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[edit | edit source]

Fișierul de intrare simonahin.txt conține pe prima linie numerele n şi p.

Date de iesire[edit | edit source]

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[edit | edit source]

1 ⩽ n ⩽ 10^18
2 ⩽ p ⩽ 5

Exemplul 1[edit | edit source]

simonahin.txt: 325 5
simonahout.txt: Datele introduse corespund restrictiilor impuse; 10

Exemplul 2[edit | edit source]

simonahin.txt: 652 1

Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<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):

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

</syntaxhighlight>

Explicatie[edit | edit source]

Numerele 325, 235, 532, 352, 253, 523 împărţite la 5 dau resturile 0,0,2,2,3,3, suma acestora fiind 10.

@@ Line 1: / Line 1: @@
 == 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.
+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 simonah.txt conține pe prima linie numerele n şi p.
+Fișierul de intrare '''simonahin.txt''' conține pe prima linie numerele '''n''' şi '''p'''.
 == Date de iesire ==
-Fișierul de ieșire simonah.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.
+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
+*1 &les; n &les; 10^18
-*2 ≤ p ≤ 5
+*2 &les; p &les; 5
 == Exemplul 1 ==
-;Intrare
+;simonahin.txt
 :325 5
+;simonahout.txt
+:Datele introduse corespund restrictiilor impuse
-;Iesire
-;Datele introduse corespund restrictiilor impuse
 :10
 == Exemplul 2 ==
-;Intrare
+;simonahin.txt
 :652 1
-;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+:Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-from itertools import permutations
+def este_input_valid(n, p):
+    return 1 <= n <= 10**18 and 2 <= p <= 5
-def suma_resturi_permutari(n, p):
+def putere_modulo(x, y, p):
-     n_str = str(n)
+     result = 1
-     cifre = list(n_str)
+    x = x % p
-    numere_permutate = set(permutations(cifre))
+     while y > 0:
+        if y % 2 == 1:
+            result = (result * x) % p
+        y = y // 2
+        x = (x * x) % p
+    return result
-     suma = 0
+def suma_resturi_permutari(n):
-     for permutare in numere_permutate:
+     suma_totala = 0
-         numar_permutat = int("".join(permutare))
-         suma += numar_permutat % p
+     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
-     return suma
+if __name__ == "__main__":
+     # Citire date de intrare
+    n, p = map(int, input("Introduceți numerele n și p, separate prin spațiu: ").split())
-def main():
+    # Verificare validitate date de intrare
-     # Citirea datelor de intrare din fișier
+    if not este_input_valid(n, p):
-    with open("simonah.txt", "r") as f:
+        print("Datele introduse nu corespund restricțiilor impuse.")
-        n, p = map(int, f.readline().split())
+     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")
-    # Calcularea și afișarea rezultatului
-    rezultat = suma_resturi_permutari(n, p)
-    # Scrierea rezultatului în fișierul de ieșire
-    with open("simonah.txt", "w") as g:
-        g.write(str(rezultat))
-if __name__ == "__main__":
-    main()
 </syntaxhighlight>