题目描述

[蓝桥杯 2024 国 A] gcd 与 lcm

题目描述

给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。

两个序列 $(a_1,a_2,\cdots,a_n)$ 与 $(b_1,b_2,\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\neq b_i$。

由于答案可能很大，请输出答案对 $998\ 244\ 353$ 取模后的结果。

输入格式

输入的第一行包含一个整数 $Q$ 表示询问次数。

接下来 $Q$ 行，每行包含三个整数 $x,y,n$ 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。

输出格式

输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。

样例 #1

样例输入 #1

3
3 6 2
12 144 3
233 251640 10

样例输出 #1

2
72
905954656

提示

对于 $40\%$ 的评测用例，$n\le 30$；
对于 $70\%$ 的评测用例，$n\le 5000$；
对于所有评测用例，$1\le Q\le 100$，$2\le n\le 10^5$，$1\le x,y\le 10^9$。

算法1

(容斥原理)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 998244353;
const int N = 35;

int primes[N], cnt;

int qmi(int a, int n)
{
    LL res = 1 % mod;

    while (n)
    {
        if (n & 1) res = res * a % mod;
        a = a * (LL)a % mod;
        n >>= 1;
    }

    return res;
}

void get_primes(int a)
{
    cnt = 0;
    for (int i = 2; i <= a / i; i ++ )
    {
        if (a % i == 0)
        {
            primes[cnt] = 0;
            while (a % i == 0)
            {
                primes[cnt] ++ ;
                a /= i;
            }
            cnt ++ ;
        }
    }

    if (a > 1) primes[cnt ++] = 1 ;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int gcd, lcm, n;
        cin >> gcd >> lcm >> n;


        get_primes(lcm / gcd);

        LL res = 1;
        for (int i = 0; i < cnt; i ++ )
        {
            LL tep = qmi(primes[i] + 1, n) % mod;
            tep = (tep - qmi(primes[i], n)) % mod;
            tep = (tep - qmi(primes[i], n)) % mod;
            tep = (tep + qmi(primes[i] - 1, n)) % mod;
            tep = (tep + mod) % mod;
            res = res * tep % mod;
        }

        printf("%lld\n", (res + mod) % mod);
    }

    return 0;
}