题解：P10580 [蓝桥杯 2024 国 A] gcd 与 lcm

yezicong1104 · 2024-10-04 21:57:49 · 题解

思路

由题得：

设 b_i=\frac{a_i}{x}，易证：

令 t=\frac{y}{x}，将其分解质因数：t=\prod_{i=1}^m p_i^{d_i}，对于每个 p_i，可以如下思考：

首先，对于 b 中的每一个数，它 p_i 的指数 c 的范围是：0 \le c \le d_i，有 d_i+1 种情况，所以一共有 (d_i+1)^n 种情况。

为了使 \gcd(b_1,b_2,\cdots,b_n)=1，至少有一个 p_i 的指数等于 0，同理，为了使 \operatorname{lcm}(b_1,b_2,\cdots,b_n) = t，至少有一个 p_i 的指数等于 d_i，也就是说上面的 (d_i+1)^n 种情况还要减去 p_i 的指数都不为 0 或都不为 d_i 的情况数。p_i 的指数都不为 0 的情况数有 d_i^n 种，p_i 的指数都不为 d_i 的情况数也是有 d_i^n 种，一共是 2d_i^n 种。但这把 p_i 的指数都既不为 0 也不为 d_i 的情况数重复算了两遍，所以还要减去一个 (d_i-1)^n，即 p_i 的指数都既不为 0 也不为 d_i 的情况数。所以一共要减去 2d_i^n-(d_i-1)^n 种情况。

综上所述，对于每个 p_i 有 (d_i+1)^n-2d_i^n+(d_i-1)^n 种情况。根据乘法原理，答案为：

时间复杂度：O(Q (\sqrt{\frac{x}{y}}+m))，易证 m\le 9，可以通过。

AC Code

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int mod = 998244353;

LL f(LL a, int b) { //快速幂
    LL res = 1;
    while (b) {
        if (b & 1) res = (res * a) % mod;
        b >>= 1, a = a * a % mod;
    } return res;
}

int main() {
    int Q;
    scanf("%d", &Q);
    vector<int> v; //存储质因数的指数
    while (Q--) {
        int x, y, n, p = 2;
        scanf("%d%d%d", &x, &y, &n);
        int t = y / x; LL pro = 1;
        v.clear(); //初始化
        while (p * p <= t) {
            if (t % p == 0) {v.push_back(0); while (t % p == 0) t /= p, v.back()++; }
            else p++;
        } if (t != 1) v.push_back(1); //剩下的是一个质数
        for (int i : v) pro = pro * (f(i + 1, n) - f(i, n) * 2 + f(i - 1, n)) % mod; //计算答案
        printf("%lld\n", (pro + mod) % mod); //加上 mod 避免负数
    }
    return 0;
}