题目分析：
首先打个暴力求一下$10^9$以内因子最多的数的因子个数，发现只有$1344$个。
由于有$ax+by=k*(a,b)$和2017年noip的结论，所以我们可以发现对于任意多个数$a_1,a_2,a_3,...,a_n$他们能组成的数是$k$倍的最大公约数，$k$任取。我们发现如果$gcd%p$不是$w$的因子那么不行，否则可行。所以把$a$数组全部模$p$，再归类为每个因子，再处理相互之间能构建出来的$gcd$，再用莫比乌斯函数做一下容斥，再处理出每个因子的因子和，再对每个输入的$w$模$p$，答案可以$O(1)$回答。
代码:
#include<bits/stdc++.h>
using namespace std; const int maxn = ;
const int MXF = ;
const int mod = 1e9+; int n,q,p;
int fac[MXF],dt[MXF],num;
int a[maxn],chs[MXF],mu[MXF];
int pw2[maxn]; int gcd(int a,int b){
if(!b) return a;
else return gcd(b,a%b);
} void divide(){
for(int i=;i*i<=p;i++){
if(p%i) continue;
if(i*i == p) fac[++num] = i;
else{
fac[++num] = i;
fac[++num] = p/i;
}
}
sort(fac+,fac+num+);
} void read(){
scanf("%d%d%d",&n,&q,&p);
divide();
for(int i=;i<=n;i++) scanf("%d",&a[i]),a[i] = gcd(a[i],p);
for(int i=;i<=n;i++){
int z = lower_bound(fac+,fac+num+,a[i])-fac;
dt[z]++;
}
for(int i=;i<=num;i++){
int hh = fac[i]; mu[i] = ;
for(int j=;j*j<=hh;j++){
int cnt = ;
while(hh % j == ) cnt++,hh/=j;
if(cnt > )mu[i] = ;
else if(cnt) mu[i] = 1ll*mu[i]*(mod-)%mod;
}
if(hh != ){mu[i] = 1ll*mu[i]*(mod-)%mod;}
}
} void work(){
pw2[] = ; for(int i=;i<=n;i++) pw2[i] = pw2[i-]*%mod;
for(int i=;i<=num;i++){
int z = ;
for(int j=i;j<=num;j++){
if(fac[j] % fac[i] == ) z+=dt[j];
}
chs[i] = (pw2[z]-)%mod;
}
for(int i=;i<=num;i++){
for(int j=i+;j<=num;j++){
if(fac[j] % fac[i]) continue;
int ct = lower_bound(fac+,fac+num+,fac[j]/fac[i])-fac;
chs[i] = chs[i]+1ll*mu[ct]*chs[j]%mod; chs[i] %= mod;
}
}
for(int i=num;i>=;i--){
for(int j=;j<i;j++){
if(fac[i] % fac[j] == ) chs[i] += chs[j],chs[i] %= mod;
}
}
for(int i=;i<=q;i++){
int x; scanf("%d",&x); x = gcd(x,p);
x = lower_bound(fac+,fac+num+,x)-fac;
printf("%d\n",chs[x]);
}
} int main(){
read();
work();
return ;
}