在线教育网站开发实例,清空wordpress数据库表,百度大数据分析平台,伪春菜 wordpress正题
题目链接:https://www.luogu.com.cn/problem/P5366 题目大意
给出一个n,G,Ln,G,Ln,G,L。 qqq次询问在1∼n1\sim n1∼n中选择若干个数字并且数字xxx必选#xff0c;要求这些数的gcdgcdgcd为GGG且lcmlcmlcm为LLL的方案数。 1≤n,G,L,x≤108,1≤q≤1051\leq n,G,L,x\leq 1…正题
题目链接:https://www.luogu.com.cn/problem/P5366 题目大意
给出一个n,G,Ln,G,Ln,G,L。
qqq次询问在1∼n1\sim n1∼n中选择若干个数字并且数字xxx必选要求这些数的gcdgcdgcd为GGG且lcmlcmlcm为LLL的方案数。
1≤n,G,L,x≤108,1≤q≤1051\leq n,G,L,x\leq 10^8,1\leq q\leq 10^51≤n,G,L,x≤108,1≤q≤105 解题思路
我们令mLG,xxG,n⌊nG⌋m\frac{L}{G},x\frac{x}{G},n\lfloor\frac{n}{G}\rfloormGL,xGx,n⌊Gn⌋那么就是求选1∼m1\sim m1∼m中的数的情况下gcd1,lcmmgcd1,lcmmgcd1,lcmm的方案。
发现对于每个mmm的分解后的质因数pcp^cpc我们选择的数的为pkp^kpk那么我们至少需要一个k0k0k0和一个kckckc。
也就是其实0km0km0km的都是不会对这个质因数产生影响的所以我们可以把一个质因子ppp分出两个状态分别是k0k0k0的和kmkmkm的有没有。
同样的我们用上面的状态SSS表示1∼n1\sim n1∼n的数字会发现SSS最多只有六百出头种不同的取值。
那么我们把这些取值拿出来把数字分成不同的类这样我们就只需要考虑每个类的数字个数了。记fi,Sf_{i,S}fi,S表示做完了前iii类时状态为SSS的方案同理gi,Sg_{i,S}gi,S则表示做完了后iii类。
这样我们可以用FWTFWTFWT快速处理出hi,Sh_{i,S}hi,S表示处理了除了第iii类以外的所有类状态为SSS时的方案。
然后再考虑这一类有一个数字必选来转移每个hi,Sh_{i,S}hi,S就知道每一类的答案了。 code
#includecstdio
#includecstring
#includealgorithm
#includeiostream
#includecctype
using namespace std;
const int N116,M610,P1e97;
int n,G,L,q,m,tot,cnt,MS,num[N];
int p[99],c[99],pos[N],pw[M],rev[M];
int f[M][N],g[M][N],h[M][N];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-48;cgetchar();}return x*f;
}
int power(int x,int b){int ans1;while(b){if(b1)ans1ll*ans*x%P;x1ll*x*x%P;b1;}return ans;
}
void FWT(int *f,int n,int op){for(int p2;pn;p1)for(int k0,lenp1;kn;kp)for(int ik;iklen;i)(f[ilen]f[i]*op)%P;return;
}
void dfs(int dep,int x,int s){if(xn)return;if(depcnt){num[s];return;}dfs(dep1,x,s|(1depcnt-1));for(int i1,pw1;ic[dep];i)pwpw*p[dep],dfs(dep1,x*pw,s|((ic[dep])dep-1));return;
}
void init(){int xm;for(int i2;ix;i)if(x%i0){p[cnt]i;while(x%i0)c[cnt],x/i;}dfs(1,1,0);MS(1cnt*2);for(int i0;iMS;i)if(num[i]){pos[i]tot;rev[tot]i;pw[tot]power(2,num[i])-1;}f[0][0]g[tot1][0]1;for(int i1;itot;i)for(int j0;jMS;j){(f[i][j]f[i-1][j])%P;(f[i][j|rev[i]]1ll*f[i-1][j]*pw[i]%P)%P;}for(int itot;i1;i--)for(int j0;jMS;j){(g[i][j]g[i1][j])%P;(g[i][j|rev[i]]1ll*g[i1][j]*pw[i]%P)%P;}for(int i0;itot;i)FWT(f[i],MS,1);for(int i1;itot1;i)FWT(g[i],MS,1);for(int i1;itot;i)for(int j0;jMS;j)h[i][j]1ll*f[i-1][j]*g[i1][j]%P;for(int i1;itot;i){FWT(h[i],MS,-1);int kpower(2,num[rev[i]]-1);for(int jMS-1;j0;j--){int rh[i][j];h[i][j]0;(h[i][j|rev[i]]1ll*r*k%P)%P;}}return;
}
signed main()
{nread();Gread();Lread();qread();n/G;mL/G;init();while(q--){int xread();if(x%G){puts(0);continue;}if(L%x){puts(0);continue;}x/G;if(xn){puts(0);continue;}int S((1cnt)-1)*(1cnt);for(int i1;icnt;i)if(x%p[i]0){int k0;S^(1icnt-1);while(x%p[i]0)x/p[i],k;if(kc[i])S|(1i-1);}cout(h[pos[S]][MS-1]P)%P\n;}return 0;
}
