自动搬运

查看原文

来自洛谷，原作者为

	Bruteforces **

搬运于2025-08-24 22:00:45，当前版本为作者最后更新于2018-07-09 14:33:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解

我们首先考虑 $n=1$ 的情况，通过打表可以发现，对于体积为 $v$ 的物品，在可以取无限次的条件下，能够取到的体积对 $P$ 取膜的值可以为

$gcd(v,P),2*gcd(v,P),3*gcd(v,P)...$

所以我们可以把这个物品的体积看做 $gcd(v,P)$，这对答案不会有任何影响。

由此我们得到启发，$O(\sqrt{P})$ 预处理出 $P$ 的每个约数，存储每个约数出现的次数。由于同一个约数多次选取对答案没有任何影响，容易得出，如果 $P$ 的一个约数出现次数为 $x$，则有 $2^x-1$ 种方案选取这个约数。

继续打表我们又可以发现，如果选取了 $P$ 的两个约数 $a_{1},a_{2}$，能够取到的值膜 $P$ 的值可以为

$gcd(a_{1},a_{2}),2*gcd(a_{1},a_{2}),3*gcd(a_{1},a_{2})...$

我们可以口胡证明，当选取约数个数大于 2 时，上式依然成立。

由此我们可以写出DP方程，设 $F[i][j]$ 表示选到 $P$ 的第 $i$ 个约数，选出的数的 gcd 值为 $P$ 的第 $j$ 个约数的方案数，则转移方程为：

$F[i][j]=F[i-1][j]+(1+\sum{_{gcd(a[k],a[i])==a[j]}F[i-1][k]})*(2^{s[i]}-1)$

其中 $a[i]$ 表示 $P$ 的第 $i$ 个约数，$s[i]$ 表示第 $i$ 个约数的出现次数。

该部分时间复杂度为 $O(M^2logM)$，空间复杂度为 $O(M^2)$ 或 $O(2M)$ （滚动数组），其中 $M$ 为 $P$ 的约数个数。

这个时候，对于每一个询问 $w_{i}$，我们容易得出答案就是

$\sum{_{a[i]|w_{i}}F[n][i]}$

但是询问数量可以达到 $10^6$ ，$M$ 最大可以达到 $10^3$ 以上，$O(qM)$ 的暴力统计依然会TLE。

事实上我们可以发现，如果一个数既是 $P$ 的约数，又是 $w_{i}$ 的约数，那么它一定是 $gcd(P,w_{i})$ 的约数，因此我们只需要统计

$\sum{_{a[i]|gcd(P,w_{i})}F[n][i]}$

而这可以在DP之后就预处理出来：

$G[i]=\sum{_{a[j]|a[i]}F[n][j]}$

因此我们可以 $O(1)$ 回答询问，这样总复杂度就是 $O(\sqrt{P}+M^2logM+q)$，这道题就可以AC啦

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N=1000010,M=10050,mod=1000000007;
int n,q,P,v[N],num[M],tot[M],cnt=0,f[2][M],g[M],now=0,sum[N];

inline void init(){
    sum[1]=2;
    for(register int i=2;i<=n;i++)sum[i]=sum[i-1]*2%mod;
    for(register int i=1;i<=n;i++)sum[i]=(sum[i]+mod-1)%mod;
    
    for(register int i=1;i<=sqrt(P);i++)if(P%i==0)num[++cnt]=i;
    for(register int i=cnt;i>1;i--)if(P/num[i]!=num[i])num[++cnt]=P/num[i];
    for(register int i=1;i<=n;i++){
        int pos=lower_bound(num+1,num+cnt+1,v[i])-num;
        tot[pos]++;
    }
    
    for(register int i=1;i<=cnt;i++)if(tot[i]){
        now^=1;
        for(register int j=1;j<=cnt;j++)f[now][j]=f[now^1][j];
        for(register int j=1;j<=cnt;j++)if(f[now^1][j]){
            int nxt=__gcd(num[j],num[i]);
            int pos=lower_bound(num+1,num+cnt+1,nxt)-num;
            (f[now][pos]+=1LL*f[now^1][j]*sum[tot[i]]%mod)%=mod;
        }
        (f[now][i]+=sum[tot[i]])%=mod;
    }
    for(register int i=1;i<=cnt;i++){
    	for(register int j=1;j<=i;j++)if(num[i]%num[j]==0){
            (g[i]+=f[now][j])%=mod;
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&q,&P);
    for(register int i=1;i<=n;i++)scanf("%d",&v[i]),v[i]=__gcd(v[i],P);
    init();
    for(register int i=1;i<=q;i++){
        int x,ans=0;scanf("%d",&x);x=__gcd(x,P);
        int pos=lower_bound(num+1,num+cnt+1,x)-num;
        printf("%d\n",g[pos]);
    }
    return 0;
}