repl.it
@moytrage/

RuStackOverflow_734145

Python

No description

fork
loading
Files
  • main.py
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def inverse(a, n):
    (t, newt, r, newr) = (0, 1, n, a)
    while newr != 0:
        quotient = r // newr
        (t, newt) = (newt, t - quotient * newt) 
        (r, newr) = (newr, r - quotient * newr)
    if r > 1:
        raise ValueError("a is not invertible")
    if t < 0:
        t = t + n
    return t

def main():
    # A * B + A + B = 0 (mod N) <=> (A + 1) * (B + 1) = 1 (mod N) <=> B = (A + 1)^(-1) - 1 (mod N)
    A = 10
    N = 997
    B = 0

    try:
        B = (inverse(A + 1, N) - 1) % N
    except ValueError:
        B = -1

    print(B)

main()
Fetching token
?