2398 - Moka

Cerința

Moca dorește să posteze pe Pbinfo a probleme de dificultate b. Durata postării celor a probleme de dificultate b este restul împărțirii lui a^b la 1999999973. Ajutați-l pe Moca să calculeze durata postării celor a probleme de dificultate b.

Date de intrare

Fișierul de intrare moka.in conține pe prima linie numerele a b, cu semnificația din enunț.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", fișierul de ieșire moka.out va conține pe prima linie numărul S, reprezentând restul împărțirii lui a^b la 1999999973. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 2 ≤ a,b ≤ 4294967296

Exemple

Exemplul 1

moka.in

2 4

ecran

Datele sunt introduse corect.

moka.out

16

Exemplul 2

memory009.in

moka.in

123456789 987654321

ecran

Datele sunt introduse corect.

moka.out

683511244

Exemplul 3

memory009.in

moka.in

4294967297 9999999999

ecran

Datele nu corespund restricțiilor impuse.

moka.out

Rezolvare

<syntaxhighlight lang="python" line="1">

1. 2398 - Moka

import sys

def valideaza_date(a: int, b: int) -> bool:

   if not (2 <= a <= 4294967296 and 2 <= b <= 4294967296):
       print("Datele nu corespund restricțiilor impuse.")
       sys.exit(0)
   print("Datele sunt introduse corect.")
   return True

def rezolva_problema(continut: str) -> str:

   a, b = map(int, continut.strip().split())

   if not valideaza_date(a, b):
       return "Datele nu corespund restricțiilor impuse."

   mod = 1999999973

   # combinam functia putere cu functia rezolva_problema
   p = b
   result = 1
   while p > 0:
       if p % 2 == 1:
           result = (result * a) % mod
       a = (a * a) % mod
       p //= 2

   return str(result)

if __name__ == "__main__":

   with open("moka.in", "r") as fin:
       continut = fin.read().strip()

   rezultat = rezolva_problema(continut)

   with open("moka.out", "w") as fout:
       fout.write(rezultat)
       fout.write("\n")

</syntaxhighlight>

Explicatie

valideaza_date(a: int, b: int) -> bool: Aceasta functie verifica daca valorile parametrilor a si b se incadreaza in intervalul [2, 4294967296]. Daca valorile sunt valide, functia afiseaza mesajul "Datele sunt introduse corect." si returneaza True. Daca valorile nu sunt valide, functia afiseaza mesajul "Datele nu corespund restrictiilor impuse." si opreste programul prin apelarea functiei sys.exit(0).

rezolva_problema(continut: str) -> str: Aceasta functie citeste continutul fisierului de intrare dat ca parametru continut si il descompune in doua numere intregi, a si b. Apoi, functia verifica daca datele sunt valide prin apelul functiei valideaza_date(). Daca datele sunt valide, functia calculeaza a^b mod 1999999973 folosind algoritmul exponentierii modulare si returneaza rezultatul ca un sir de caractere.

if __name__ == "__main__": : Aceasta instructiune verifica daca programul este rulat ca fisier independent si apoi executa codul din interiorul acestei instructiuni. In acest caz, programul citeste continutul fisierului "moka.in", calculeaza rezultatul folosind functia rezolva_problema() si apoi scrie rezultatul in fisierul "moka.out". Aceasta instructiune este utilizata pentru a evita rularea codului dintr-un modul la importare.