自己思考的：
一个(v_i)，可以产生(gcd(p,v_i))的贡献
然后多个贡献，枚举所有的(gcd)？
SOL：
1e9 以内的数不同质因子不会超过10个，且所有质因子指数和不会超过30，实测约数个数最多的自然是仅有1536个约数
显然是要用DP
(f[i][j])表示前i个p的约数，gcd为j时的答案（可以滚动数组优化）
直接枚举转移（刷表）
注意：设s[i]表示(gcd(p,v)=i)的个数，则不选1种，选(2^{s[i]}-1)种
(ans=sum_{factor[i]|gcd(p,w)}f[n][i])
(g[i]=sum_{factor[j]|factor[i]}f[n][j])
即可(O(1))回答
时间复杂度(O(sqrt p+M^2log_M+Q),M)为p的约数个数
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
#define ll long long
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
const int N=1e6+4,mod=1e9+7;
int n,p,Q,cur,tot;
int g[N],f[2][N],fac[N],s[N],v[N],mi[N];
int main(){
n=read();Q=read();p=read();
for(int i=1;i<=n;i++)v[i]=read();
for(int i=1;i*i<=p;i++){
if(p%i)continue;
fac[++tot]=i;
if(i<p/i)fac[++tot]=p/i;
}
sort(fac+1,fac+tot+1);
mi[0]=1;
int x;
for(int i=1;i<=n;i++){
mi[i]=(mi[i-1]<<1)%mod;
x=lower_bound(fac+1,fac+tot+1,gcd(p,v[i]))-fac;
s[x]++;
}
for(int i=1;i<=tot;i++){
if(!s[i])continue;
cur^=1;
memcpy(f[cur],f[cur^1],sizeof(f[cur^1]));
for(int j=1;j<=i;j++){
if(!f[cur^1][j])continue;
x=lower_bound(fac+1,fac+tot+1,gcd(fac[j],fac[i]))-fac;
(f[cur][x]+=(ll)f[cur][j]*(mi[s[i]]-1)%mod)%=mod;
}
(f[cur][i]+=mi[s[i]]-1)%=mod;
}
for(int i=1;i<=tot;i++)
for(int j=1;j<=i;j++)
if(fac[i]%fac[j]==0)(g[i]+=f[cur][j])%=mod;
while(Q--){
x=lower_bound(fac+1,fac+tot+1,gcd(p,read()))-fac;
cout<<g[x]<<"
";
}
return (0-0);
}