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

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

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.