最大公约数与最小公倍数序列(GCD and LCM Sequences) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
using namespace std;

const long long MOD = 998244353;

long long qpow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    long long x, y, n;
    cin >> x >> y >> n;
    if (y % x != 0) {
        cout << 0 << "\n";
        return;
    }
    long long m = y / x;
    long long ans = 1;
    for (long long d = 2; d * d <= m; ++d) {
        if (m % d == 0) {
            int e = 0;
            while (m % d == 0) {
                m /= d;
                e++;
            }
            long long ways = (qpow(e + 1, n) - 2LL * qpow(e, n) + qpow(e - 1, n)) % MOD;
            if (ways < 0) ways += MOD;
            ans = ans * ways % MOD;
        }
    }
    if (m > 1) {
        long long ways = (qpow(2, n) - 2LL) % MOD;
        if (ways < 0) ways += MOD;
        ans = ans * ways % MOD;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q;
    if (!(cin >> Q)) return 0;
    while (Q--) solve();
    return 0;
}