Finding inverse

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

map<ll, ll> f;


ll modpow(ll a, ll b, ll M) {
	if (b == 0) return 1;
	ll t = modpow(a, b/2, M);
	t = (t * t) % M;
	if (b%2==1) t = (t * a) % M;
	return t;
}

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

ll totient(ll M) {
	ll tot = 1;
	for (auto [p, a] : f) {
		tot = (tot * modpow(p, a-1, M)) % M; 
		tot = (tot * (p-1)) % M;
	}
	return tot;
}

int main() {
	ll x, M;
	cin >> x >> M;
	ll g = gcd(x, M);
	if (g != 1) {
		cout << -1 << endl;
		return 0;
	}
	ll y = M;
	for (ll k=2; k*k <= y; k++) {
		while (y%k == 0) {
			f[k]++;
			y /= k;
		}
	}
	if (y > 1) f[y]++; 
	ll tot = totient(M-1);
	ll inv = modpow(x, (tot+M-2)%(M-1), M);
	cout << inv << endl;
	return 0;
	
}

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