首页 > 代码库 > HDU1695:GCD（容斥原理+欧拉函数+质因数分解）好题
HDU1695:GCD（容斥原理+欧拉函数+质因数分解）好题
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1695
题目解析：
Given 5 integers: a, b, c, d, k, you‘re to find x in a...b, y in c...d that GCD(x, y) = k.
题目又说a==c==1,所以就是求[1,b]与[1,d]中gcd等于k的个数，因为若gcd(x,y)==z,那么gcd(x/z,y/z)==1，又因为不是z的倍数的肯定不是，所以不是z的倍数的可以直接去掉，所以只要将b和d除以k，然后就转化成了求两个范围中互质的对数了。即求[1,b/k],与[1,d/k]中互质的数目，让b<d,又因为 (x=5, y=7) and (x=7, y=5) are considered to be the same.
所以先求[1,b/k]中互质的数目，即phi[1]+phi[2]+phi[3].....+phi[b/k]（其中phi[i]为i的欧拉函数值），再从区间[b/k+1,d/k]枚举与区间[1,b/k]中互质的数目。其中求与区间[1,b/k]中互质的数目可以通过容斥原理求得与区间[1,b/k]中不互质的数目，相减便可以求得结果。这题折腾了一中午，一直TLE，代码在后面贴了，之后看大神的博客知道了哪里超时的原因，每个数的质因子可以在打表求欧拉函数的时候顺便求出来，一种哈希的思想，这样就不用在枚举的时候每一个数在求一遍他的质因子了，好题！
代码如下：（608ms）
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>using namespace std;typedef __int64 ll;ll sum,phi[100010];int cnt[100010][11],f[100010],a,b,c,d,x;void init(){ memset(f,0,sizeof(f)); for(int i=1; i<=100000; i++) { phi[i]=0; f[i]=0; } phi[1]=1; for(int i=2; i<=100000; i++) { if(!phi[i]) { for(ll j=i; j<=100000; j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); cnt[j][f[j]++]=i;//算是哈希吧,很精辟啊，这种写法要学习 } } phi[i]+=phi[i-1]; }}ll gcd(ll A,ll B){ return B==0?A:gcd(B,A%B);}void dfs(ll now,ll num,ll lcm,ll &coun,int key){ lcm=cnt[key][now]/gcd(cnt[key][now],lcm)*lcm; if(num&1) { coun+=b/lcm; } else { coun-=b/lcm; } for(ll i=now+1; i<f[key]; i++) dfs(i,num+1,lcm,coun,key);}int main(){ int T,K=0; init(); scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&x); if(x == 0 || x > b || x > d) { printf("Case %d: 0\n",++K); continue; } b/=x; d/=x; sum=0; if(b>d) swap(b,d); sum+=phi[b]; for(int i=b+1; i<=d; i++) { ll coun=0; for(int j=0; j<f[i]; j++) { dfs(j,1,cnt[i][j],coun,i); } sum+=(b-coun); } printf("Case %d: %I64d\n",++K,sum); } return 0;}
TLE的：（TLE了一中午 3000ms++)
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>#include <math.h>using namespace std;typedef __int64 ll;ll a,b,c,d,x,sum,top,cnt[100010],we;//********int phi[100010],su[100010],prime[100010];void init(){ we=0; prime[we++]=2; su[0]=su[1]=0; su[2]=1; for(int i=3; i<100005; i++) if(i%2==0) su[i]=0; else su[i]=1; double t=sqrt(100005*1.0); for(ll i=3; i<=t; i++) { if(su[i]) { for(ll j=i*i; j<100005; j=j+i) { su[j]=0; } } } for(ll i=3; i<=100003; i++) { if(su[i]) prime[we++]=i; } memset(phi,0,sizeof(phi)); phi[1]=1; for(ll i=2; i<=100003; i++) { if(!phi[i]) { for(ll j=i; j<=100003; j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } }}ll gcd(ll A,ll B){ return B==0?A:gcd(B,A%B);}void dfs(ll now,ll num,ll lcm,ll &coun){ lcm=cnt[now]/gcd(cnt[now],lcm)*lcm; if(num&1) { coun+=b/lcm; //printf("hsum======%I64d\n",sum); } else { coun-=b/lcm; } for(ll i=now+1; i<top; i++) dfs(i,num+1,lcm,coun);}void cal(ll key,ll &coun){ top=0; ll KK=0; for(ll i=prime[0]; i<=key; i=prime[++KK]) { if(key%i==0) { cnt[top++]=i; key/=i; while(key%i==0) key/=i; } } if(key!=1) { cnt[top++]=key; } for(ll i=0; i<top; i++) { dfs(i,1,cnt[i],coun); }}int main(){ int T,K=0; init(); scanf("%d",&T); while(T--) { scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&x); if(x == 0 || x > b || x > d) { printf("Case %d: 0\n",++K); continue; } b/=x; d/=x; sum=0; if(b>d) swap(b,d); //cout<<"b=="<<b<<" "<<"d=="<<d<<endl; for(int i=1; i<=b; i++) { sum+=phi[i]; } //cout<<"sumsss=="<<sum<<endl; for(ll i=b+1; i<=d; i++) { if(su[i]) { sum+=b; continue; } ll coun=0; cal(i,coun); sum+=(b-coun); } printf("Case %d: %I64d\n",++K,sum); } return 0;}
HDU1695:GCD（容斥原理+欧拉函数+质因数分解）好题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。