看到 GCD / LCM，果断莫反（雾
但是发现莫反并没有办法处理强制选 \(X\) 的情况……
换个方向。
值域 \(10^8\)，所以 \(L\) 最多有 \(8\) 个质因子。
所以考虑状压 DP。
根据数论套路，令 \(N \gets \left\lfloor\frac NG\right\rfloor,L \gets \frac LG\)。当然，若 \(G \not \mid L\) 直接无解。
那么问题变为在 \(1\dots N\) 内选若干个互质的正整数，强制选择 \(X\)，使得它们的 LCM 为 \(L\) 的方案数。
也即这些数的每个质因子的指数的最小值为 \(0\)，最大值为 \(L\) 对应的指数。
考虑如此状压一个数：前一半表示这个数每个质因子指数是否为 \(0\)，后一半表示这个数每个质因子指数是否等于 \(L\) 对应的指数。
将 \(1 \dots N\) 内 \(L\) 的约数拿出来，按照状态分组，发现合法的状态并不多。
设 \(f_{0/1,i,j}\) 表示考虑了第 \(i\) 种状态之前 / 之后所有状态，总状态为 \(j\) 的方案数。
选择一种状态的贡献是这种状态对应的整数的子集个数。
强制选择一个 \(X\) 即合并 \(f_{0,i}\) 和 \(f_{1,i}\)，其中 \(i\) 为 \(X\) 的状态，这个可以 FWT 合并。
注意此时第 \(i\) 种状态的贡献要考虑强制选择了至少一个数。
又是一道在洛谷不开 O2 跑不过的题（
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
using namespace std;
const int C = 8;
const int N = 16;
const int S = 1 << N;
const int CNT = 700;
const int mod = 1e9 + 7;
inline int fpow(int a,int b)
{
int ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
return ret;
}
int n,g,l,q,s;
inline void fwt(int *a,int type,int n)
{
for(register int w = 2,m = 1;w <= n;w <<= 1,m <<= 1)
for(register int i = 0;i < n;i += w)
for(register int j = 0;j < m;++j)
a[i | j | m] = type == 1 ? add(a[i | j | m],a[i | j]) : dec(a[i | j | m],a[i | j]);
}
struct Factor
{
int fac[C + 5],e[C + 5],cnt;
inline Factor(int n = 1)
{
cnt = 0;
for(register int i = 2;i * i <= n;++i)
{
!(n % i) && (fac[++cnt] = i,e[cnt] = 0);
for(;!(n % i);n /= i,++e[cnt]);
}
n > 1 && (fac[++cnt] = n,e[cnt] = 1);
fac[cnt + 1] = 0x3f3f3f3f;
}
} L;
inline int state(int n)
{
Factor f(n);
int s = (1 << L.cnt) - 1;
for(register int i = 1,j;i <= f.cnt;++i)
j = lower_bound(L.fac + 1,L.fac + L.cnt + 1,f.fac[i]) - L.fac,
s &= ~(1 << j - 1),s |= ((f.e[i] == L.e[j]) << L.cnt + j - 1);
return s;
}
int w[CNT + 5],cnt,c[S + 5],val[CNT + 5];
int f[2][CNT + 5][S + 5],ans[CNT + 5];
int main()
{
scanf("%d%d%d%d",&n,&g,&l,&q);
if(l % g)
{
for(;q;--q)
puts("0");
return 0;
}
n /= g,l /= g,L = Factor(l),s = 1 << 2 * L.cnt;
for(register int i = 1;i <= n;++i)
!(l % i) && ++c[state(i)];
for(register int i = 0;i < s;++i)
c[i] && (w[++cnt] = i,val[cnt] = (fpow(2,c[i]) + mod - 1) % mod);
f[0][1][0] = f[1][cnt][0] = 1;
for(register int i = 1;i < cnt;++i)
for(register int j = 0;j < s;++j)
f[0][i + 1][j] = add(f[0][i + 1][j],f[0][i][j]),
f[0][i + 1][j | w[i]] = (f[0][i + 1][j | w[i]] + (long long)f[0][i][j] * val[i]) % mod;
for(register int i = cnt;i > 1;--i)
for(register int j = 0;j < s;++j)
f[1][i - 1][j] = add(f[1][i - 1][j],f[1][i][j]),
f[1][i - 1][j | w[i]] = (f[1][i - 1][j | w[i]] + (long long)f[1][i][j] * val[i]) % mod;
for(register int i = 1;i <= cnt;++i)
{
fwt(f[0][i],1,s),fwt(f[1][i],1,s);
for(register int j = 0;j < s;++j)
f[0][i][j] = (long long)f[0][i][j] * f[1][i][j] % mod;
fwt(f[0][i],-1,s);
for(register int j = 0;j < s;++j)
if((j | w[i]) == s - 1)
ans[i] = add(ans[i],f[0][i][j]);
ans[i] = (long long)ans[i] * fpow(2,c[w[i]] - 1) % mod;
}
for(int x;q;--q)
{
scanf("%d",&x);
if(x % g)
{
puts("0");
continue;
}
x /= g;
if(l % x || x > n)
{
puts("0");
continue;
}
printf("%d\n",ans[lower_bound(w + 1,w + cnt + 1,state(x)) - w]);
}
}