分解质因数与容斥原理

思路:

设n个数，它们的最大公因子为G，最小公倍数为L，问有多少种不同的方法还原这个数列。

质因数分解：
每个数a_i都可以分解为质因数的乘积，即：
a_i=p₁^ei1⋅p₂^ei2⋅…⋅p_k^eik，
其中p₁,p₂,…,p_k是质数，eij是质数pj在ai中的指数。

最大公因子G是所有a_i共有的质因数的最小指数的乘积，

最小公倍数L是所有a_i中每个质因数的最大指数的乘积。

可以知道，L一定是G的倍数。

每个质因数都是独立的，所以可以算出每个质因数在n个位置的填写情况，然后将每个质因数情况相乘。

对于质因数p，设在最大公因子中相乘l次，在最小公倍数中相乘r次，那么每个数中，相乘次数需满足[l, r]，共有cnt = r - l + 1种情况。

不考虑重叠，n个位置，有cntⁿ中方法，

注意：在n个数中需至少出现一次p相乘l次，至少出现一次p相乘r次，才能得到G和L。

在总情况中，减去没出现过l，减去没出现r的情况，再加上l和r都没出现过的情况，得到：

cntⁿ - (cnt-1)ⁿ - (cnt - 1)ⁿ + (cnt -2)ⁿ

其实可以发现，我们只关心cnt的大小，所以令z = y / x，计算z的每个质因子相乘的个数即可。

注意事项:

在计算结果，减的过程中会出现负的情况，加mod后再减。

参考代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
ll ksm(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b & 1) res = a * res % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
void solve() {
	ll x, y, n;
	cin >> x >> y >> n;
	if(y % x) {
		cout << 0 << endl;
		return;
	}
	y /= x;
	vector<ll> v;
	int t = 0;
	for(int i = 2; i <= sqrt(y) && y != 1; i++) {
		if(y % i) {
			continue;
		}
		while(y % i == 0) {
			t++;
			y /= i;
		}
		if(t) v.push_back(t);
		t = 0;
	}
	if(y != 1) v.push_back(1);
	ll ans = 1;
	for(auto e:v) {
		ll t = ksm(e + 1, n);
		if(t > 1) {
			t = (t - ksm(e, n) + mod) % mod;
			t = (t - ksm(e, n) + mod) % mod;
			t = (t + ksm(e - 1, n)) % mod;
		}
		ans = ans * t % mod;
	}
	cout << ans << endl;
}
int main() {
	int T;
	cin >> T;
	while(T--) solve();
	return 0;
}