Finding inverse

import sys
import math

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



def sieve_primes(n):
    primes = [2]
    for i in range(3, n // 2 + 1, 2):
        is_prime = True
        for j in primes:
            if i % j == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    return primes


def euler(n, primes):
    div = []
    for p in primes:
        if n % p == 0:
            div.append(p)
    # print(div)
    if not div:
        return n - 1
    c = n
    for d in div:
        c *= (d - 1)
        c //= d
    return c


def fast_exp(a, b, mod):
    if b == 0:
        return 1
    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())
if math.gcd(a, M) != 1:
    print(-1)
else:
    e = euler(M, sieve_primes(M))
    print(fast_exp(a, e - 1, M))

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: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: ACCEPTED