自动搬运

查看原文

来自洛谷，原作者为

	HYdroKomide I hate unfair games.

搬运于2025-08-24 22:59:22，当前版本为作者最后更新于2024-06-23 23:24:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

给定一个数列的元素个数 $n$、最大公约数 $x$ 和最小公倍数 $y$，问有多少种不同的方法还原这个数列。

思路：

不难发现数列中所有元素必然为 $x$ 的倍数，它们之间产生的差异就在于 $\dfrac{y}{x}$。

设 $\dfrac{y}{x}=t$，将其分解质因数：$t=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$。不难发现，每个质因数对答案的贡献是独立的。不妨考虑 $p_1$ 的情况。

对于 $p_1$，要使得答案序列的最大公约数为 $x$，必定需要有至少一个元素，其 $p_1$ 质因子的指数为 $0$。同理，要使得答案序列最小公倍数为 $y$，必定需要有至少一个元素，其 $p_1$ 质因子的指数为 $k_1$。

使用容斥思想。先考虑没有限制的情况，$p_1$ 的指数可以取 $[0,k_1]$ 的所有整数，答案个数为 $(k_1+1)^n$。

接着，要减去所有被限制的情况。为了满足最大公约数的条件，至少需要有一个元素 $p_1$ 的指数为 $0$，因此需要减去所有 $p_1$ 指数在 $[1,k_1]$ 的情况。此类情况总数为 $k_1^n$。同理，需要减去所有 $p_1$ 指数在 $[0,k_1-1]$ 的情况，此类情况总数也为 $k_1^n$。

最后，注意到指数全部在 $[1,k_1-1]$ 区间的情况被减去了两次，需要加回来一次。因此在原式上加回 $(k_1-1)^n$。

因此，对于质因子 $p_1$，其贡献为 $(k_1+1)^n-2k_1^n+(k_1-1)^n$。由于不同质因子之间独立，答案为 $\prod_{i=1}^m(k_i+1)^n-2k_i^n+(k_i-1)^n$。

观察到 $m$ 最多不超过 $10$，可忽略不计。最终时间复杂度为 $O(Q\sqrt \dfrac{y}{x})$（分解质因数）。

易错点：取模运算相减后可能导致出现负数，需要在输出时对模数相加。

程序如下：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=35,MOD=998244353;
int q,cnt,p[N],k[N];
void getprime(int x){//分解质因数
    cnt=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            k[++cnt]=0;//提前清空
            while(x%i==0){
                x/=i;
                k[cnt]++;
            }
        }
    }
    if(x!=1)k[++cnt]=1;//注意如果没分解完，说明剩下的是单独的一个质数
}
long long qpow(long long x,long long y){
    long long ret=1;
    while(y){
        if(y&1)ret=ret*x%MOD;
        y>>=1;
        x=x*x%MOD;
    }
    return ret;
}
int main(){
    scanf("%d",&q);
    while(q--){
        int x,y,n;
        long long ans=1;
        scanf("%d%d%d",&x,&y,&n);
        getprime(y/x);
        for(int i=1;i<=cnt;i++){
            long long tmp=qpow(k[i]+1,n);
            tmp=(tmp-qpow(k[i],n))%MOD;
            tmp=(tmp-qpow(k[i],n))%MOD;
            tmp=(tmp+qpow(k[i]-1,n))%MOD;
            tmp=(tmp+MOD)%MOD;
            ans=ans*tmp%MOD;
        }
        printf("%lld\n",(ans+MOD)%MOD);//注意再加一次模数，防止出负
    }
    return 0;
}

THE END