Finding inverse

import sys
import math

sys.setrecursionlimit(10**6)
input = sys.stdin.readline



def factors(n):
    f = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            f.append(i)
            while n % i == 0:
                n /= i
        i += 1
    if n != 1:
        f.append(n)
    return f


def euler(n, f):
    if f[-1] == n:
        return n - 1
    c = n
    for i in f:
        c *= (i - 1)
        c //= i
    return c


def fast_exp(a, b, mod):
    g = 1
    while b > 1:
        if b % 2 == 1:
            g = (g * a) % mod
            b -= 1
        a = (a * a) % mod
        b //= 2
    return (a * g) % mod


a, M = map(int, input().split())
e = euler(M, factors(M))
r = fast_exp(a, e - 1, M)
if (a * r) % M == 1:
    print(r)
else:
    print(-1)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED