Editing 2059 - porumbei (section)

== 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>