Finding inverse

#include <bits/stdc++.h>

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

// Type Aliases for 1D and 2D vectors with initialization
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val))              // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val

using namespace std;

void print_vector(vector<int> &x)
{
    for (int v : x)
    {
        cout << v << " ";
    }
    cout << "\n";
}

void print_matrix(vector<vector<int>> &matrix)
{
    cout << "\n"
         << "----------------" << "\n";
    for (vector<int> row : matrix)
    {
        print_vector(row);
    }
    cout << "\n"
         << "----------------" << "\n";
}

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;
}

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 euler_totient(int n)
{
    vector<int> prime_factors = factors(n);
    // print_vector(prime_factors);
    int result = 1;
    int last_factor = 2;
    int last_factor_count = 0;
    for (int factor : prime_factors)
    {
        if (factor == last_factor)
        {
            last_factor_count++;
        }
        else
        {
            result *= (last_factor - 1);
            for (int i = 1; i < last_factor_count; i++)
            {
                result *= last_factor;
            }
            last_factor = factor;
            last_factor_count = 1;
        }
    }
    result *= (last_factor - 1);
    for (int i = 1; i < last_factor_count; i++)
    {
        result *= last_factor;
    }
    return result;
}

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

int main()
{
    int a, M;

    cin >> a >> M;

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

    int euler_tot = euler_totient(M);
    cout << modpow(a, euler_tot - 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