记录编号	576980	评测结果	AAAAAAAAAA
题目名称	最大公因数取模	最终得分	100
用户昵称	该账号已注销	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-19 19:52:44	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
long long t, a, b, n, mod = 1000000007;
unsigned long long A;
unsigned long long ans = 0;

long long power(long long a, long long x, long long m) {
	if (x == 0)
		return 1;
	if (x == 1)
		return a % m;
	if (x % 2 == 0) {
		long long p = power(a, x / 2, m) % m;
		return (p % m * p % m) % m;
	} else
		return ((power(a, x - 1, m) % m) * (a % m)) % m;
}

int main() {
	freopen("gcmod.in", "r", stdin);
	freopen("gcmod.out", "w", stdout);
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		cin >> a >> b >> n;
		unsigned long long y = abs(a - b);
		if (y == 0) {
			cout << (power(a, n, mod) % mod + power(b, n, mod) % mod) % mod << endl;
			continue;
		}
		bool l = 0;
		for (int i = 1; i <= sqrt(y); i++) {
			if (y % i != 0)
				continue;
			long long x1 = (power(a, n, i) % i + power(b, n, i) % i) % i;
			if (x1 == 0) {
				ans = i;
			}
			long long k = y / i;
			long long x2 = (power(a, n, k) % k + power(b, n, k) % k) % k;
			if (x2 == 0) {
				if (k > i) {
					cout << k << endl;
					l = 1;
					break;

				}
			}
		}
		if (l == 0)
			cout << ans << endl;
	}
	return 0;
}