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):
    c = 0
    for i in range(1, n + 1):
        if math.gcd(n, i) == 1:
            c += 1
    if c == n:
        return c - 1
    else:
        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)
    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: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: ACCEPTED