题解 P10580

· · 题解

题意：

给定一个数列的元素个数 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