Editing 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''
:
<br>


== Rezolvare == 
<syntaxhighlight lang="python" line="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.