显然存在方案的数一定是 L 的因数, 考虑对其因子预处理答案, O(1)回答.
考虑每个质因子, 设其在 g 中有 x 个, l 中有 y 个, 则要求所有选中的数该质因子个数都在 [x,y] 中, 且存在数的质因子个数为 x,y. 对于后一个限制, 显然可以简单地容斥, 即[x,y]-[x+1,y]-[x,y-1]+[x+1,y-1], 枚举这个至多是 48 的, 这个取最大值时因子个数是 28. 暴力枚举数数即可. 复杂度总之 O(能过).
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- using namespace std;
- #define P 1000000007
- #define ll long long
- int read()
- {
- int x=0,f=1;char c=getchar();
- while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
- while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
- return x*f;
- }
- int n,g,l,u,m,prime[20],cnt[2][20],d[10000],ans[10000],p[10000][20],q[10000][20],a[20],tot,t,sum;
- int ksm(int a,int k)
- {
- int s=1;
- for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
- return s;
- }
- void get(int k,int s)
- {
- if (k>t) {sum++;return;}
- ll x=ksm(prime[k],cnt[0][k]);
- for (int i=cnt[0][k];i<=cnt[1][k];i++)
- {
- if (s*x<=n) get(k+1,s*x);else break;
- x=1ll*x*prime[k];
- }
- }
- void build(int k,int s)
- {
- if (k>t)
- {
- p[++tot][0]=s;
- for (int i=1;i<=t;i++) p[tot][i]=a[i];
- return;
- }
- ll x=ksm(prime[k],cnt[0][k]);
- for (int i=cnt[0][k];i<=cnt[1][k];i++)
- {
- a[k]=i;
- if (s*x<=n) build(k+1,s*x);else break;
- x=1ll*x*prime[k];
- }
- }
- void calc(int op)
- {
- //for (int i=1;i<=t;i++) cout<<prime[i]<<''<<cnt[0][i]<<' '<<cnt[1][i]<<endl;cout<<endl;
- sum=0;get(1,1);
- for (int i=1;i<=tot;i++)
- {
- bool flag=1;
- for (int j=1;j<=t;j++)
- if (p[i][j]<cnt[0][j]||p[i][j]>cnt[1][j]) {flag=0;break;}
- if (flag)
- {
- ans[i]+=op*ksm(2,sum-1);
- if (ans[i]<0) ans[i]+=P;if (ans[i]>=P) ans[i]-=P;
- }
- }
- }
- void dfs(int k,int op)
- {
- if (k>t) {calc(op);return;}
- dfs(k+1,op);
- cnt[0][k]++;dfs(k+1,-op);
- cnt[1][k]--;dfs(k+1,op);
- cnt[0][k]--;dfs(k+1,-op);
- cnt[1][k]++;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("bzoj5019.in","r",stdin);
- freopen("bzoj5019.out","w",stdout);
- const char LL[]="%I64d\n";
- #else
- const char LL[]="%lld\n";
- #endif
- n=read(),g=read(),l=read(),m=read();
- if (l%g) {for (int i=1;i<=m;i++) printf("0\n");return 0;}
- u=l;
- for (int i=2;i*i<=u;i++)
- if (u%i==0)
- {
- prime[++t]=i,cnt[1][t]=1;u/=i;
- while (u%i==0) cnt[1][t]++,u/=i;
- }
- if (u>1) prime[++t]=u,cnt[1][t]=1;
- u=g;
- for (int i=1;i<=t;i++)
- while (u%prime[i]==0) u/=prime[i],cnt[0][i]++;
- build(1,1);
- for (int i=1;i<=tot;i++) d[i]=p[i][0];
- sort(d+1,d+tot+1);
- for (int i=1;i<=tot;i++)
- for (int j=0;j<=t;j++)
- q[i][j]=p[i][j];
- for (int i=1;i<=tot;i++)
- {
- int x=lower_bound(d+1,d+tot+1,q[i][0])-d;
- for (int j=0;j<=t;j++) p[x][j]=q[i][j];
- }
- dfs(1,1);
- while (m--)
- {
- int x=read(),y=lower_bound(d+1,d+tot+1,x)-d;
- if (d[y]!=x) {printf("0\n");continue;}
- else printf("%d\n",ans[y]);
- }
- return 0;
- }
BZOJ5019 SNOI2017 遗忘的答案(容斥原理)
来源: http://www.bubuko.com/infodetail-2905166.html