Luogu

LOJ

分析

先来考虑 $n=1$ 的情况，可以发现所有能取到的体积为 $k\cdot\gcd(v,P)$ 。于是我们可以直接把体积设成 $\gcd(v,P)$ 。

这样子所有体积都是 $P$ 的约数了。考虑预处理出 $P$ 的所有约数，然后求出每种约数在体积中的出现次数。

注意到一条性质：重复选取相同的体积对答案没有影响。于是假设第 $i$ 个约数有 $s_i$ 个，那么这个约数的方案数就是 $2^{s_i}-1$。

接着可以发现，如果选取了一些体积 $a_1,a_2,...,a_d$ ，那么所有能够取到的体积为 $k\cdot\gcd(a_1,a_2,...,a_d)$ 。

那么可以考虑 DP。设 $f_{i, j}$ 表示选到了 $P$ 的第 $i$ 个约数，选出的数的 $\gcd$ 值为 $P$ 的第 $j$ 个约数的方案数。转移类似于背包。

考虑如何回答询问。对于一个询问 $w_i$ ，可以发现答案就是 $\sum_{r_j | w_i} f_{cnt, j}$ ，这里的 $r$ 表示 $P$ 的约数。

那么满足条件的 $r_j$ 一定是 $\gcd(w_i,P)$ 的约数。于是答案可以写成 $\sum_{r_j|\gcd(w_i,P)} f_{cnt, j}$。

预处理 $g_i=\sum_{r_j|r_i}f_{n, j}$ ，即可快速回答询问。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int mod=1e9+7;

int n,q,P;
int v[N],w[N],pw[N];
int frac[N],s[N],cnt=0;
int f[2][N],g[N];

int main() {
    n=read(),q=read(),P=read();
    for (re int i=1;i<=n;++i) v[i]=__gcd(read(),P);
    for (re int i=1;i<=q;++i) w[i]=__gcd(read(),P);

    for (re int i=(pw[0]=1);i<=n;++i) pw[i]=2ll*pw[i-1]%mod;
    for (re int i=1;i<=n;++i) pw[i]=(pw[i]-1+mod)%mod;

    for (re int i=1;i*i<=P;++i) {
        if (P%i) continue;
        frac[++cnt]=i;
        if (i*i!=P) frac[++cnt]=P/i;
    }
    sort(frac+1,frac+cnt+1);

    for (re int i=1;i<=n;++i) {
        int x=lower_bound(frac+1,frac+cnt+1,v[i])-frac;
        ++s[x];
    }

    int now=0;
    for (re int i=1;i<=cnt;++i) {
        if (!s[i]) continue;
        now^=1; int pre=now^1;
        for (re int j=1;j<=cnt;++j) f[now][j]=f[pre][j];
        for (re int j=1;j<=cnt;++j) {
            if (!f[pre][j]) continue;
            int nxt=__gcd(frac[i],frac[j]);
            int x=lower_bound(frac+1,frac+cnt+1,nxt)-frac;
            f[now][x]=(f[now][x]+1ll*f[pre][j]*pw[s[i]])%mod;
        }
        f[now][i]=(f[now][i]+pw[s[i]])%mod;
    }

    for (re int i=1;i<=cnt;++i)
        for (re int j=1;j<=i;++j)
            if (frac[i]%frac[j]==0) g[i]=(g[i]+f[now][j])%mod;

    for (re int i=1;i<=q;++i) {
        int x=lower_bound(frac+1,frac+cnt+1,w[i])-frac;
        printf("%d\n",g[x]);
    }
    return 0;
}