Finding inverse

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i=a;i<(b);++i)
#define all(x) begin(x),end(x)
#define sz(x) int((x).size())
using ul = unsigned int;
using ull = unsigned long long;

ul phi(ul n) {
  if (n <= 1) return 1;
  ul x = 1;
  for (ul m = 2; m*m <= n; ++m) {
    if (n % m == 0) {
      x *= m-1;
      for (n /= m; n % m == 0; n /= m) {
        x *= m;
      }
    }
  }
  if (n != 1) x *= n-1;
  return x;
}

ul M;

ul mpow(ull a, ull p) {
  a %= M;
  ull r = 1;
  while (p != 0) {
    if (p & 1) {
      r *= a; r %= M;
    }
    a *= a; a %= M;
    p >>= 1;
  }
  return r;
}

int main() {
  ul a;
  cin >> a >> M;
  if (M > 1 && __gcd(a,M) == 1) {
    cout << mpow(a,phi(M)-1) << '\n';
  } else {
    cout << "-1\n";
  }
}

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