Luogu

LOJ

分析

首先特判掉 $G\nmid L$ 的情况。

为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。

我们先不管那个必须选 $X$ 的条件，想一想怎么做。

注意到值域只有 $10^8$，即最多只有 $8$ 个质因子，可以考虑状压 DP。

先考虑如何设状态。先将 $L$ 分解质因数，每个数对应的状态的前 $8$ 位表示该数中每个质因子的指数是否为 $0$，后 $8$ 位表示该数中每个质因子的指数是否和 $L$ 相同。

注意到可能会有一些数对应的状态相同。我们预处理出所有 $L$ 的 $[1,n]$ 内的约数，然后把状态相同的分在一组中。可以发现组数不会太大（大概在 $600$ 左右）。

这样子就可以 DP 了。设 $dp_{i,j}$ 表示前 $i$ 组状态为 $j$ 的方案数。转移考虑当前组选还是不选：如果选的话当前组有 $2^{cnt}-1$ 种方案，状态会或上该组的状态；不选则状态不会有变化。

现在考虑必须选 $X$ 的限制。可以先求出不包含 $X$ 所在的组的方案数，然后再将所有或上 $X$ 的状态为全集的那些位置加起来，再乘上 $X$ 所在组的方案数（因为 $X$ 必须选所以为 $2^{cnt-1}$）。

现在的问题是如何求出不包含 $X$ 所在的组的方案数。设 $f_{i,j}$ 表示前 $i$ 组状态为 $j$ 的方案数， $g_{i,j}$ 表示 $i$ 组之后所有组状态为 $j$ 的方案数，求法和上面的 DP 相同。设 $X$ 所在组为 $x$，则我们只需要合并 $f_{x-1}$ 和 $g_{x+1}$ 即可。可以发现合并的过程其实就是或卷积，于是 FWT 即可。

预处理出所有强制包含某个组的答案，最后询问时直接找到 $X$ 对应的组即可。

具体实现可以看代码。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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 mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,G,L,Q;
vector<int> v;
int p[10],c[10],pcnt=0;
int num[650],sum[650],s[1<<16],cnt=0;
int f[650][1<<16],g[650][1<<16],h[650][1<<16],ans[650];

void devide(int x) {
    for (int i=2;i*i<=x;++i) {
        if (x%i) continue;
        p[++pcnt]=i;
        while (x%i==0) x/=i,++c[pcnt];
    }
    if (x>1) p[++pcnt]=x,c[pcnt]=1;
}

int calc(int x) {
    int res=0;
    for (int i=1;i<=pcnt;++i) {
        int y=0;
        while (x%p[i]==0) x/=p[i],++y;
        if (y==0) res|=1<<(i-1);
        if (y==c[i]) res|=1<<(i-1+pcnt);
    }
    return res;
}

void FWT_or(int* A,int n,int op) {
    for (int i=1;i<n;i<<=1)
        for (int j=0;j<n;j+=i<<1)
            for (int k=0;k<i;++k) {
                if (op==1) A[i+j+k]=(A[i+j+k]+A[j+k])%mod;
                else A[i+j+k]=(A[i+j+k]-A[j+k]+mod)%mod;
            }
}

int main() {
    n=read(),G=read(),L=read(),Q=read();
    if (L%G) { while (Q--) puts("0"); return 0; }
    L/=G,n/=G; devide(L);
    for (int i=1;i<=n&&i*i<=L;++i) {
        if (L%i) continue;
        v.push_back(i);
        if (L/i<=n&&i*i!=L) v.push_back(L/i);
    }
    for (int i:v) ++s[calc(i)];
    int lim=1<<(pcnt<<1);
    for (int i=0;i<lim;++i)
        if (s[i]) num[++cnt]=i,sum[cnt]=qpow(2,s[i])-1;
    f[0][0]=g[cnt+1][0]=1;
    for (int i=0;i<cnt;++i)
        for (int S=0;S<lim;++S) {
            f[i+1][S]=(f[i+1][S]+f[i][S])%mod;
            f[i+1][S|num[i+1]]=(f[i+1][S|num[i+1]]+1ll*f[i][S]*sum[i+1])%mod;
        }
    for (int i=cnt+1;i>1;--i)
        for (int S=0;S<lim;++S) {
            g[i-1][S]=(g[i-1][S]+g[i][S])%mod;
            g[i-1][S|num[i-1]]=(g[i-1][S|num[i-1]]+1ll*g[i][S]*sum[i-1])%mod;
        }
    for (int i=0;i<=cnt;++i) FWT_or(f[i],lim,1);
    for (int i=1;i<=cnt+1;++i) FWT_or(g[i],lim,1);
    for (int i=1;i<=cnt;++i)
        for (int S=0;S<lim;++S)
            h[i][S]=1ll*f[i-1][S]*g[i+1][S]%mod;
    for (int i=1;i<=cnt;++i) FWT_or(h[i],lim,-1);
    for (int i=1;i<=cnt;++i) {
        for (int S=0;S<lim;++S)
            if ((S|num[i])==lim-1) ans[i]=(ans[i]+h[i][S])%mod;
        ans[i]=1ll*ans[i]*qpow(2,s[num[i]]-1)%mod;
    }
    while (Q--) {
        int x=read();
        if (x%G) { puts("0"); continue; }
        x/=G;
        if (L%x||x>n) { puts("0"); continue; }
        int p=lower_bound(num+1,num+cnt+1,calc(x))-num;
        printf("%d\n",ans[p]);
    }
    return 0;
}