Finding inverse

input/code.cpp: In function 'int main()':
input/code.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

void add(int &a, int b, int m) {
  a += b;
  if (a >= m) {
    a -= m;
  }
}

int mul(int a, int b, int m) {
  return 1LL * a * b % m;
}

int mod_pow(int a, int b, int m) {
  int r = 1;
  for (; b > 0; a = mul(a, a, m), b >>= 1) {
    if (b & 1) {
      r = mul(r, a, m);
    }
  }
  return r;
}

int a, m;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> a >> m;
  if (gcd(a, m) != 1) {
    cout << -1 << '\n';
    return 0;
  }
  // calc phi(m)
  // ans = a^(phi(m) - 1)
  // factorize m first
  vector<int> p;
  int q = m;
  for (int i = 2; i * i <= q; i++) {
    if (q % i == 0) {
      p.emplace_back(i);
      while (q % i == 0) {
        q /= i;
      }
    }
  }
  if (q > 1) {
    p.emplace_back(q);
  }
  long long ans = m;
  for (int mask = 1; mask < (1 << p.size()); mask++) {
    int pr = 1;
    for (int i = 0; i < p.size(); i++) {
      if (mask >> i & 1) {
        pr *= p[i];
      }
    }
    if (__builtin_popcount(mask) & 1) {
      ans -= m / pr;
      ans %= (m - 1);
      if (ans < 0) {
        ans += m - 1;
      }
    } else {
      ans += m / pr;
      ans %= (m - 1);
    }
  }
  ans--;
  if (ans < 0) {
    ans += m - 1;
  }
  cout << mod_pow(a, ans, m) << '\n';
  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