Finding inverse

#include <bits/stdc++.h>

typedef long long ll;

int gcd(int aa, int bb) {
  if (aa == 0)
    return bb;
  return gcd(bb % aa, aa);
}

ll totient(ll nn) {
  ll result = nn;
  for (ll pp = 2; pp * pp <= nn; ++pp) {
    if (nn % pp == 0) {
      while (nn % pp == 0)
        nn /= pp;
      result -= result / pp;
    }
  }
  if (nn > 1)
    result -= result / nn;
  return result;
}

ll modPow(ll x, ll n, ll 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;
}

int isPrime(ll nn) {
  if (nn % 2 == 0)
    return 0;
  ll pp = 3;
  while (pp * pp < nn) {
    if (nn % pp == 0) {
      return 0;
    }
    pp += 2;
  }
  return 1;
}

int main() {
  ll num, mod;
  std::cin >> num >> mod;
  ll ret = 0;
  if (isPrime(mod)) {
    ret = modPow(num, mod - 2, mod);
  } else {
    ll toti = totient(mod);
    ret = modPow(num, toti - 1, mod);
  }

  if ((num * ret) % mod != 1) {
    ret = -1;
  }

  std::cout << ret << std::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