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

· · 题解

题目链接：https://www.luogu.com.cn/problem/P10580

注：思路和代码参考自@览遍千秋在 10 月 7 日洛谷秋令营的课件与代码。

这是一道数学题。

思路

知识点：

  1. 快速幂；
  2. 埃氏筛；
  3. 唯一分解定理：
    • 任意给定整数 n，可以被唯一的分解为
    • 其中 p_i 为质因数，c_i 为其指数。
  4. 乘法原理；

  5. 容斥原理。

    • 我们将每个 a_i 除以 x，将其变成 \rm{gcd} 为 1，\rm{lcm} 为 \frac {y}{x}；
    • 对于 1 ≤ i ≤ n，ai 在质因数 p_j 的指数上可以取 0 至 c_j；
    • 根据乘法原理，p_j 对答案的贡献为 (c_j + 1)^n；
    • 但是，我们要排除两个非法值：
      • 若对于所有的 1 ≤ i ≤ n，指数均不为 0；
      • 若对于所有的 1 ≤ i ≤ n，指数均不为 c_j。
    • 根据容斥原理，考虑其重复情况，p_j 对答案的贡献为：{f(j)} = (c_j + 1)^n - 2 × {c_j}^n + (c_j - 1)^n，最后再求 f(j) 的积就可以了！这里就用到快速幂了。

现在思路讲完了，接下来出现的是你们最期待的代码了！！！

code:

// 2024.10.20 20:48
#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int MOD = 998244353;
int q, x, y, n;
bool prime[N];
// 埃氏筛，预处理
void ai_shai()
{
    for (int i = 2; i <= 100000; i++)
    {
        if (prime[i])
            continue;
        for (int j = 2 * i; j <= 100000; j += i)
            prime[j] = true;
    }
}
// 快速幂，作用见上文
int q_pow(int x, int p)
{
    int res = 1;
    while (p)
    {
        if (p & 1)
            res = res * x % MOD;
        p >>= 1;
        x = x * x % MOD;
    }
    return res;
}
signed main()
{
    ai_shai();
    cin >> q;
    while (q--)
    {
        cin >> x >> y >> n;
        y /= x;
        int limit = y;
        vector<int> v;
        // 唯一分解定理
        for (int i = 2; i * i <= limit; i++)
        {
            if (prime[i])
                continue;
            int cnt = 0;
            while (y % i == 0)
            {
                cnt++;
                y /= i;
            }
            if (cnt != 0)
                v.push_back(cnt);
        }
        if (y > 1)
            v.push_back(1);
        int ans = 1;
        for (auto ci : v)
        {
            int tmp = ((q_pow(ci + 1, n) - 2 * q_pow(ci, n)) % MOD + q_pow(ci - 1, n)) % MOD;
            tmp = (tmp + MOD) % MOD;
            ans = ans * tmp % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}
// 完结散花！！！