Tenka1 Programmer Contest: ModularPowerEquation!! (WA解法(は？))

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_f

ある十分大きいx(A<10^18とかなら100程度でよい)をとればA^x≡A^(x+φ(M))(modM)が成立します。
A^A^A^A...を考えるとKのmodφ(M)とmodMの値が求められるので、あとはユークリッドの互除法をして解を構成すればよい…なんですが、値がでかくなりすぎてWA…どうやって小さくするんだろう…。

ll phi(ll M) {
	ll A = M;
	for(ll i = 2; i * i <= A; i++) {
		if(A % i == 0) {
			M = M / i * (i - 1);
			while(A % i == 0) A /= i;
		}
	}
	if(A != 1) M = M / A * (A - 1);
	return M;
}

ll extgcd(ll a, ll b, ll& x, ll& y) { //get(ax + by = gcd(a, b))
	if(b == 0) {
		x = 1; y = 0;
		return a;
	}
	ll res = extgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return res;
}

ll mod_pow(ll a, ll n, ll mod) { //get a^n mod
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2, mod);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}

int Q;
ll A, M;


ll loop(ll A, ll M) {
	if(M == 1) return 10000;
	ll K = loop(A, phi(M));
	ll tK = mod_pow(A, K, M);
	return tK + (tK < 100 ? M : 0);
}

void solve() {
	cin >> Q;
	while(Q--) {
		cin >> A >> M;
		ll pM = phi(M);
		ll K = loop(A, M) % M;
		ll pK = loop(A, pM) % pM;
		debug(K, pK);
		ll x, y;
		ll g = extgcd(M, pM, x, y);
		debug(M, pM, x, y, g);
		ll l = M * pM / g;
		ll ans = (((M / g) * x * pK + (pM / g) * y * K) % l + l) % l + l;
		cout << ans << "\n";
		debug(mod_pow(A, ans, M), ans % M);
	}
}

mod系の問題、すぐオーバーフローして嫌になる…。