时间限制: 2s 内存限制: 192MB 提交: 52 解决: 11
题目描述
给定两个数 x, y ，求有多少种不同的长度为 n 的序列 (a1, a2, · · · , an)，其所有元素的最大公约数为 x 且最小公倍数为 y 。
两个序列 (a1, a2, · · · , an) 与 (b1, b2, · · · , bn) 不同，是指存在至少一个位置 i满足 ai , bi 。
由于答案可能很大，请输出答案对 998244353 取模后的结果。
输入格式
输入的第一行包含一个整数 Q 表示询问次数。
接下来 Q 行，每行包含三个整数 x,y,n 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。
输出格式
输出 Q 行，每行包含一个整数，依次表示每个询问的答案。
样例输入
3
3 6 2
12 144 3
233 251640 10样例输出
2
72
905954656分析与推理
最大公约数 (GCD) 为 x：序列中的每个元素 ai 必须是 x 的倍数，即 ai=kx，其中 k 是某个正整数。
最小公倍数 (LCM) 为 y：序列中所有元素的最小公倍数 y 必须满足 LCM(a1,a2,…,an)=y。
由于每个 ai 是 x 的倍数，我们可以表示为 ai=kx。因此，y 也必须是 x 的倍数，即 y=mx，其中 m 是某个正整数。
唯一性：两个序列不同是指存在至少一个位置 i 使得 ai=bi。
数量计算：由于 ai=kx，并且 y=mx，我们需要找出所有可能的 k 使得 LCM(kx1,kx2,…,kxn)=mx。
注意到 LCM(kx1,kx2,…,kxn)=k?LCM(x1,x2,…,xn)，并且 LCM(x1,x2,…,xn) 必须是 km 的倍数。
因此，我们需要找出所有可能的 k，使得 km 是一个整数，并且 LCM(x1,x2,…,xn)=km。
解决方案
为了计算满足条件的序列的数量，我们需要遍历所有可能的 k 值，并计算可能的组合数量。
对于每个询问 (x,y,n)，首先计算 m=xy。
遍历 k 的所有可能值（k 必须是 m 的因子），计算可能的组合数量。
由于每个位置可以独立选择 k 的倍数，总数量将是这些选择数的乘积，并对 998244353 取模。
代码
#include <iostream>
#include <vector>
#include <cmath>
const int MOD = 998244353;
// 函数：计算 n 的所有因子
std::vector<int> get_factors(int n) {
std::vector<int> factors;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
factors.push_back(i);
if (i != n / i) {
factors.push_back(n / i);
}
}
}
return factors;
}
// 快速幂计算 (base^exp) % mod
long long power_mod(long long base, long long exp, int mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
int main() {
int Q;
std::cin >> Q;
while (Q--) {
int x, y, n;
std::cin >> x >> y >> n;
int m = y / x;
std::vector<int> factors = get_factors(m);
long long total_count = 0;
for (int k : factors) {
if (m % k == 0) {
// 每个位置可以独立选择 k 的倍数，共 (m/k)^n 种选择
long long count = power_mod(m / k, n, MOD);
total_count = (total_count + count) % MOD;
}
}
std::cout << total_count << std::endl;
}
return 0;
}解释
获取因子：get_factors 函数用于计算一个数的所有因子。
快速幂：power_mod 函数用于计算快速幂，避免直接计算大数的幂导致溢出。
主函数：读取输入。
计算 m=x/y。
遍历 m 的所有因子 k，计算每个因子对应的组合数量，并累加结果。
输出每个询问的答案。
通过这种方法，我们可以高效地计算满足条件的序列数量，并对结果进行取模。