由裴蜀定理，子集S有解当且仅当gcd(S,P)|w。
一个显然的dp是设f[i][j]为前i个数gcd为j的选取方案。注意到这里的gcd一定是P的约数，所以状态数是n√P的。然后可以通过这个得到gcd是j约数的选取方案。复杂度O(n√PlogP)。
考虑优化。注意到每个数取gcd后的贡献仅与其和P的gcd有关，而这又一定是P的约数，所以本质不同的物品数量也是O(√P)。那么上面的dp就可以优化到O(PlogP)了。当然这里的P是P的约数个数的平方，这显然是远远达不到P的。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 1000010 #define K 2010 #define P 1000000007 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,k,d[K],cnt[K],f[K][K],ans[K],t; inline void inc(int &x,int y){x+=y;if (x>=P) x-=P;} int main() { #ifndef ONLINE_JUDGE freopen("bzoj5302.in","r",stdin); freopen("bzoj5302.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(),k=read(); for (int i=1;i*i<=k;i++) if (k%i==0) { d[++t]=i;cnt[t]=1; if (i*i!=k) d[++t]=k/i,cnt[t]=1; } sort(d+1,d+t+1); for (int i=1;i<=n;i++) (cnt[lower_bound(d+1,d+t+1,gcd(k,read()))-d]<<=1)%=P; f[0][0]=1; for (int i=1;i<=t;i++) for (int j=0;j<=t;j++) inc(f[i][j],f[i-1][j]),inc(f[i][lower_bound(d+1,d+t+1,gcd(d[i],d[j]))-d],1ll*f[i-1][j]*(cnt[i]-1)%P); for (int i=1;i<=t;i++) for (int j=1;j<=i;j++) if (d[i]%d[j]==0) inc(ans[i],f[t][j]); for (int i=1;i<=m;i++) printf("%d ",ans[lower_bound(d+1,d+t+1,gcd(k,read()))-d]); return 0; }