Finding inverse

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

#include <bits/stdc++.h>
 
using namespace std;
 
 
long long fastpow(long long x, long long n, long long mod) {
    if (n == 0) 
        return 1;
    if (n & 1 == 1) 
        return x * fastpow(x, n-1, mod) % mod;
    long long halfpow = fastpow(x, n/2, mod) % mod;
    return halfpow*halfpow % mod;
}
 
void sieve_of_Eratosthenes(vector<long long>& 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;
    }
}
 
list<long long> primes_factors(long long n) {
    vector<long long> sieve(n+1);
    sieve_of_Eratosthenes(sieve);
    list<long long> primes;
 
    long long p;
    while (n > 1)
    {
        p = sieve[n];
        if (p == 0) {
            primes.push_front(n);
            break;
        }
        primes.push_front(p);
        n /= p;
    }
    return primes;
}
 
int phi(int n)
{
    int result = n; 
 
    for(int p = 2; p * p <= n; ++p)
    {
        if (n % p == 0) { 
            while (n % p == 0) n /= p;  
            result -= result / p;
        }
    }
 
    if (n > 1) result -= result / n;
    return result;
}
 
 
bool are_coprimes(long long a, long long b) {
    return fastpow(a, phi(b), b) == 1;
}
 
 
int main() {
    long long a, M;
    cin >> a >> M;
 
    long long phiM = phi(M);
 
    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