Finding inverse

input/code.cpp: In function 'long long unsigned int fastpow(long long unsigned int, long long unsigned int, long long unsigned int)':
input/code.cpp:18:15: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   18 |     if (n & 1 == 1) return x * fastpow(x, n-1, mod) % mod;
      |             ~~^~~~
input/code.cpp: In function 'void sieve_of_Eratosthenes(std::vector<long long unsigned int>&)':
input/code.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int x = 2; x < sieve.size(); x++) {
      |                     ~~^~~~~~~~~~~~~~
input/code.cpp:28:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int u = 2*x; u < sieve.size(); u += x) sieve[u] = x;
      |...

#include <bits/stdc++.h>

using namespace std;

#define debug(...) Debug(#__VA_ARGS__, __VA_ARGS__);
template <typename... Args>
void Debug(const char* names, Args&&... args) {
   std::cerr << names << " = ";
   ((std::cerr << args << ", "), ...) << "\b\b " << std::endl;
}
#define ll long long
#define ull unsigned long long
#define vi vector<int>

// O(log n)
ull fastpow(ull x, ull n, ull mod) {
    if (n == 0) return 1;
    if (n & 1 == 1) return x * fastpow(x, n-1, mod) % mod;
    ull halfpow = fastpow(x, n/2, mod) % mod;
    return halfpow*halfpow % mod;
}

// O(n * log log n)
void sieve_of_Eratosthenes(vector<ull>& sieve) {
    fill(sieve.begin(), sieve.end(), 0);
    for (int x = 2; x < sieve.size(); x++) {
        if (sieve[x]) continue;
        for (int u = 2*x; u < sieve.size(); u += x) sieve[u] = x;
    }
}

// Find prime factorss using Eratosthenes sieve
list<ull> primes_factors(ull n) {
    debug(n)
    vector<ull> sieve(n+1);
    sieve_of_Eratosthenes(sieve);
    list<ull> primes;

    ull p;
    while (n > 1)
    {
        debug(n)
        p = sieve[n];
        if (p == 0) {
            primes.push_front(n);
            break;
        }
        primes.push_front(p);
        n /= p;
    }
    return primes;
}

// Euler's Totient Function O(phi(n log n))
int phi(int n)
{
    // Initialize result as n
    int result = n; 
 
    // Consider all prime factors of n and subtract their multiples from result
    for(int p = 2; p * p <= n; ++p)
    {
        // Check if p is a prime factor.
        if (n % p == 0) { 
            // If yes, then update n and result
            while (n % p == 0) n /= p;  
            result -= result / p;
        }
    }
 
    // If n has a prime factor greater than sqrt(n) (There can be at-most one such prime factor)
    if (n > 1) result -= result / n;
    return result;
}


bool are_coprimes(ull a, ull b) {
    return fastpow(a, phi(b), b) == 1;
}


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

    ull phiM = phi(M);

    // If a and not coprimes
    if (fastpow(a, phiM, M) != 1) {
        cout << -1 << endl;
        return 0;
    }

    cout << fastpow(a, phiM-1, M) << 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