链接：https://www.luogu.com.cn/problem/P5366
题目描述:有\(n\)个数\(1\)到\(n\)，给定\(q\)组询问，每组询问形如求选择一些数且必须选\(x\)且最大公约数为\(G\),最小公倍数为\(L\)的方案数。
题解:首先\(G,L\)可化作\(G/L,1\),\(G\)除\(L\)不为\(0\)是直接输\(-1\).\(x\)的限制比较讨厌，先把它去掉。
由于\(1...n\)是无序的，\(dp\)不好设状态，那么我们可以对于每一个质因子状压\(dp\):
令\(dp_{S}\)表示一个大小为\(2n\)的质因子集合,第\(i\)位表示\(gcd\)中是否\(p_{i}^0\),第\(i+n\)位表示\(lcm\)中是否\(p_{i}^{max_{i}}\)(\(max_{i}\)为\(G/L\)的质因子\(p_{i}\)的次数)，打一下表可以发现状态数很少，只有\(600\)左右的样子。
然后考虑加上\(x\)的限制，那么\(x\)就必须选，且能选\([1,x-1]\)与\([x+1,n]\)这一部分，那么我们可以预处理所有\([1,x]\),\([x,n]\)的状压\(dp\)数组，然后将它们合并，合并即按位或，\(FWT\)即可。
#include<iostream>
#include<cstdio>
#include<ctime>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#define mod 1000000007
using namespace std;
long long n,tong[100001],sum,res,len,length,Ll,Gg,A[100001],B[100001],C[100001],f[701][1<<16],g[701][1<<16],N[1<<16],F[9],G[9];
long long fast_pow(long long a,int b)
{
if (b==0)
return 1;
if (b&1)
return fast_pow(a*a%mod,b/2)*a%mod;
else
return fast_pow(a*a%mod,b/2);
}
void FWT(long long limit,long long *a,int type)
{
for (int j=1;j<=(1<<(limit-1));j*=2)
for (int i=0;i<=(1<<limit)-1;++i)
if (i&j)
a[i]=(a[i]+type*a[i-j])%mod;
return;
}
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
int used[1<<16];
long long fpow[29],SU[701];
inline void solve(int X)
{
res=0;
int cnt;
for (int j=1;j<=length;++j)
{
cnt=0;
while (X%F[j]==0)
{
X/=F[j];
cnt++;
}
if (cnt==G[j])
res+=(1<<(j+length-1));
if (cnt==0)
res+=(1<<(j-1));
}
if (!used[res])
{
tong[++len]=res;
N[len]=1;
used[res]=len;
}
else
N[used[res]]++;
return;
}
signed main()
{
int q;
n=read(),Ll=read(),Gg=read(),q=read();
if (Gg%Ll!=0)
{
while (q--)
puts("0");
return 0;
}
Gg/=Ll;
n/=Ll;
int X=Gg,Y,cnt;
for (int i=2;i*i<=Gg;++i)
if (X%i==0)
{
F[++length]=i;
while (X%i==0)
{
X/=i;
G[length]++;
}
}
fpow[0]=1;
for (int i=1;i<=28;++i)
fpow[i]=fpow[i-1]*2%mod;
if (X>1&&X<=n)
{
F[++length]=X;
G[length]++;
}
for (int i=1;i*i<=Gg&&i<=n;++i)
if (Gg%i==0)
{
solve(i);
if (i*i!=Gg&&Gg/i<=n)
solve(Gg/i);
}
f[0][0]=1;
for (int i=1;i<=len;++i)
{
for (int j=0;j<=(1<<(2*length))-1;++j)
f[i][j|tong[i]]=(f[i][j|tong[i]]+f[i-1][j]*(fpow[N[i]]-1)%mod)%mod;
for (int j=0;j<=(1<<(2*length))-1;++j)
f[i][j]=(f[i][j]+f[i-1][j])%mod;
}
g[len+1][0]=1;
for (int i=len;i>=1;--i)
{
for (int j=0;j<=(1<<(2*length))-1;++j)
g[i][j|tong[i]]=(g[i][j|tong[i]]+g[i+1][j]*(fpow[N[i]]-1)%mod)%mod;
for (int j=0;j<=(1<<(2*length))-1;++j)
g[i][j]=(g[i][j]+g[i+1][j])%mod;
}
for (int i=1;i<=len;++i)
{
for (int j=0;j<=(1<<(2*length))-1;++j)
A[j]=f[i-1][j];
for (int j=0;j<=(1<<(2*length))-1;++j)
B[j]=g[i+1][j];
FWT(2*length,A,1);
FWT(2*length,B,1);
for (int j=0;j<=(1<<(2*length))-1;++j)
C[j]=A[j]*B[j]%mod;
FWT(2*length,C,-1);
for (int j=0;j<=(1<<(2*length))-1;++j)
if ((j|tong[i])==(1<<(2*length))-1)
SU[i]=(SU[i]+C[j]*fpow[N[i]-1]%mod)%mod;
}
while (q--)
{
X=read();
if (X%Ll!=0)
{
puts("0");
continue;
}
X/=Ll;
if (Gg%X!=0||X>n)
{
puts("0");
continue;
}
res=0;
Y=X;
for (int i=1;i<=length;++i)
{
cnt=0;
while (Y%F[i]==0)
{
Y/=F[i];
cnt++;
}
if (cnt==G[i])
res+=(1<<(i+length-1));
if (cnt==0)
res+=(1<<(i-1));
}
Y=0;
for (int i=1;i<=len;++i)
if (tong[i]==res)
Y=i;
printf("%lld\n",(SU[Y]+mod)%mod);
}
return 0;
}