首页 > 代码库 > [容斥原理] hdu 1695 GCD
[容斥原理] hdu 1695 GCD
题意:
给你a,b,c,d,k问 x∈[a,b] y∈[c,d],gcd(x,y)=k 的个数
然后重复算一种 也就是 x=1,y=2和x=2,y=1是一样的。
思路:
首先将b/k,d/k 就转换成了 x∈[a,b] y∈[c,d],gcd(x,y)=1的个数
然后我们枚举其中一个长度较小的区间
找另一个区间与它互质的数
因为数很多,需要预处理一下每个数的质因子
然后就是容斥定理搞了!
然后要注意0的情况!
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; #define ll __int64 #define N 100000 int ss[N+2],v[N+2]; int mark[N+5][10],mcnt[N+5],c[12]; int ssb() { int cnt=0; memset(ss,0,sizeof(ss)); for(int i=2;i<=N;i++) { if(ss[i]==0) { for(int j=i+i;j<=N;j+=i) ss[j]=1; v[cnt++]=i; } } return cnt; } ll dfs(int k,int x,int lit,int a,int b) { ll ans=0; if(x==lit) { int tep=1; for(int i=0;i<lit;i++) tep*=c[i]; return b/tep-a/tep; } for(int i=k+1;i<mcnt[a];i++) { c[x]=mark[a][i]; ans+=dfs(i,x+1,lit,a,b); } return ans; } ll solve(int x,int y) { ll ans=0; for(int i=1;i<=mcnt[x];i++) { if(i%2) ans+=dfs(-1,0,i,x,y); else ans-=dfs(-1,0,i,x,y); } return ans; } int main() { int t,cas=1,sscnt; cin>>t; sscnt=ssb(); memset(mcnt,0,sizeof(mcnt)); for(int i=0;i<sscnt;i++) { for(int j=v[i];j<=N;j+=v[i]) { mark[j][mcnt[j]++]=v[i]; } } while(t--) { int a,b,c,d,k; scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); if(k==0) { printf("Case %d: %d\n",cas++,0); continue; } b/=k; d/=k; if(b>d) swap(b,d); ll ans=(b==0?0:d); for(int i=2;i<=b;i++) { ans+=d-i-solve(i,d); } printf("Case %d: %I64d\n",cas++,ans); } return 0; }
[容斥原理] hdu 1695 GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。