Finding inverse

#include <bits/stdc++.h>

using namespace std;

bool prime(int n) {
    if (n < 2) return false;
    for (int x = 2; x*x <= n; x++) {
        if (n%x == 0) return false;
    }
    return true;
}

vector<int> factors(int n) {
    vector<int> f;
    for (int 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 gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

int modpow(int x, int n, int 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;
}

int main() {

    int a, M;
    cin >> a >> M;

    // 0 <= a < M <= 1e9

    bool coprime = gcd(a, M) == 1;

    if (coprime) {

        if (prime(M)) {

            int inv = modpow(a, M-2, M);
            cout << inv << endl;

        } else {

            int phi = 1;
            vector<int> f = factors(M);

            multiset<int> alphas;
            for (int factor : f)
                alphas.insert(factor);
            
            int i = 0;
            int n = (int) f.size();
            while (i < n) {
                int alpha = alphas.count(f[i]);
                phi *= (modpow(f[i], alpha - 1, M) * (f[i] - 1)) % M;
                i += alpha;
            }

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

    } else {
        cout << -1 << 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