Finding inverse

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

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;


typedef long double C;
typedef complex<C> P;
#define X real()
#define Y imag()

#define sz(x) (ll)(x).size()

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define REP(i,a,b) for (ll i = a; i < b; i++)

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

ll modpow(ll x, ll n, ll m) {
    if (n == 0) return 1%m;
    long long u = modpow(x,n/2,m);
    u = (u*u)%m;
    if (n%2 == 1) u = (u*x)%m;
    return u;
}

vector<ll> factors(ll n) {
    vector<ll> f;
    for (ll x = 2; x*x <= n; x++) {
        while (n%x == 0) {
            f.push_back(x);
            n /= x;
        }
    }
    if (n > 1) f.push_back(n);
    
    return f;
}

int main() {
    ll a, M;
    cin >> a >> M;

    if(gcd(a,M) != 1) {
        cout << -1 << endl;
        return 0;
    }
    
    ll phi = 1;

    vector<ll> fact = factors(M);
    map<ll, ll> nb_appear;

    for(ll p : fact) {
        nb_appear[p]++;
    }

    for(auto [p, alpha] : nb_appear){
        phi *= pow(p,alpha-1) * (p-1);
    }


    cout << modpow(a,phi-1,M) << endl;
}

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