2059 - porumbei

Cerința

A venit primăvara și a început sezonul de concursuri pentru porumbei. La un concurs fiecare participant trebuie să trimită câte doi porumbei. Fiecare porumbel are ataşat pe picior un inel care conţine un număr. Într-o noapte, înainte de un concurs, Tavi, un mare pasionat de porumbei, are un vis în care o zână bună îi spune codurile celor doi porumbei pe care, dacă îi va trimite, va câştiga concursul. Cum Tavi este un mare uituc, dimineaţa îşi mai aminteşte doar prima parte a visului în care zâna îi spune 2 numere a şi n. El îşi mai aminteşte că numerele X şi Y (pe care le-a uitat) de pe inelele porumbeilor sunt puse în aşa fel încât rezultatul aX – aY să fie divizibil cu n. X și Y sunt numerele de pe inelele porumbeilor pe care îi va trimite la concurs.

Dându-se doua numere a şi n, să se afişeze cele două numere X şi Y cu Y minim.

Date de intrare

Fișerul porumbei.in are pe prima linie numerele a și n, separate printr-un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul porumbei.out conține două numere naturale distincte, în ordine crescătoare și separate printr-un spațiu, ce reprezintă valorile minime ale lui X și Y astfel încât rezultatul a^X – a^Y să fie divizibil cu n.

Î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 ≤ n ≤ 2.000.000
• 2 ≤ a ≤ 2.000.000
• 0 ≤ X < Y

Exemple

Exemplul 1

porumbei.in

4 10

ecran

Datele sunt introduse corect.

porumbei.out

1 3

Exemplul 2

porumbei.in

4 7

ecran

Datele sunt introduse corect.

porumbei.out

0 4

Exemplul 3

porumbei.in

3 5000000

ecran

Datele nu corespund restricțiilor impuse.

porumbei.out

Rezolvare

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

1. 12059 - porumbei

def validate_input(m, n, a):

   """
   Validates the input values for the pigeonhole principle algorithm.

   Args:
       m (int): The value of the base.
       n (int): The value of the modulus.
       a (int): The starting value.

   Raises:
       ValueError: If any of the input values are invalid.

   Returns:
       None.
   """
   if not (2 <= n <= 2000000):
       raise ValueError("Invalid value for n!")
   if not (2 <= a <= 2000000):
       raise ValueError("Invalid value for a!")

def pigeonhole_principle(m, n):

   """
   Implements the pigeonhole principle algorithm for finding the smallest non-negative integers p and q such that
   m^p ≡ m^q (mod n), where 2 <= m, n <= 2,000,000.

   Args:
       m (int): The value of the base.
       n (int): The value of the modulus.

   Returns:
       A tuple containing the values of p and q.
   """
   v = bytearray(262145)  # The vector used to mark the found remainders
   v[1 // 8] = v[1 // 8] | (1 << (1 % 8))  # Mark the remainder 1 as found

   a = 1
   r = 1
   while True:
       r = (r * m) % n
       if v[r // 8] & (1 << (r % 8)) != 0:  # If the bit for the remainder is already set
           q = a  # Then there was a previous remainder equal to r, so we stop
           break
       else:
           v[r // 8] = v[r // 8] | (1 << (r % 8))
       a += 1

   if r == 1:
       p = 0
   else:
       r1 = 1
       for i in range(1, q):
           r1 = (r1 * m) % n
           if r1 == r:
               p = i
               break

   return (p, q)

if __name__ == "__main__":

   try:
       with open("porumbei.in", "r") as f, open("porumbei.out", "w") as g:
           m, n = map(int, f.readline().strip().split())
           a = 2  # Set a to the minimum valid value
           validate_input(m, n, a)  # Validate the input values
           print("Datele sunt introduse corect.")

           p, q = pigeonhole_principle(m, n)  # Run the algorithm

           g.write(f"{p} {q}\n")  # Write the output to file
   except ValueError as e:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie

validate_input(m, n, a) Această funcție validează valorile de intrare m, n, și a pentru a se asigura că îndeplinesc restricțiile impuse. Mai exact, funcția verifică dacă n și a sunt între 2 și 2,000,000 inclusiv, iar dacă nu, se ridică o excepție ValueError cu un mesaj corespunzător. Dacă valorile de intrare sunt valabile, funcția nu returnează nimic.

pigeonhole_principle(m, n) Această funcție implementează algoritmul principiului cutiei poștale pentru a găsi cele mai mici numere naturale pozitive p și q astfel încât m^p ≡ m^q (mod n). În primul rând, se inițializează un vector de byte-uri v care va fi folosit pentru a marca resturile găsite. Se marchează restul 1 ca fiind găsit, deoarece (m^0) % n = 1. Apoi, se calculează restul r = (m^1) % n și se marchează ca fiind găsit în vectorul v. Se crește contorul a și se calculează următorul rest r = (m^a) % n. Acest lucru continuă până când se găsește un rest care a mai fost întâlnit anterior. Atunci, se oprește și se returnează perechea (p, q) de valori, unde p este valoarea minimă a lui a astfel încât m^p ≡ r (mod n) și q este valoarea minimă a lui a astfel încât m^q ≡ r (mod n) și q > p.

if __name__ == "__main__": Această condiție verifică dacă script-ul este rulat ca program principal sau este importat ca modul în alt script Python. În acest caz, script-ul este rulat ca program principal. Acest bloc conține citirea datelor de intrare din fișier, apelarea funcției validate_input() pentru a valida datele de intrare și apelarea funcției pigeonhole_principle() pentru a rula algoritmul. În cazul în care datele nu sunt valide, se va ridica o excepție ValueError care va fi prinsă în blocul except.

try-except Aceasta este o structură de control care permite prinderea și gestionarea excepțiilor în Python. În acest cod, folosim try-except pentru a prinde excepțiile ValueError care sunt ridicate de funcția validate_input(). Dacă o excepție ValueError este prinsă, se afișează un mesaj corespunzător.