Finding inverse

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define IOS ios_base::sync_with_stdio(0), cin.tie(0)
const int INF = 1001001001;
const int MAXN = 100'000;
const char br = '\n';
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;


int nxt() {
	int x;
	cin >> x;
	return x;
}

vector<int> factors(int n) {
	vector<int> f;
	for (int x = 2; x * x <= n; x++) {
		while (n % x == 0) {
			f.push_back(x);
			x /= x;
		}
	}
	if (n > 1) 
		f.push_back(n);
	return f;
}

int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}

int phi(int n) {
	int result = n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n/= i;
			result -= result / i;
		}
	}
	if (n > 1)
		result -= result / n;
	return result;
}

ll binpow(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}


int main() {
	IOS;

	auto a = nxt();
	auto m = nxt();

	if (gcd(a, m) != 1) {
		cout << -1 << br;
		return 0;
	}

	auto totient = phi(m);
	cout << binpow(a, totient - 1, m) << br;

	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