首页 > 代码库 > HDU2588:GCD（欧拉函数的应用）
HDU2588:GCD（欧拉函数的应用）
题目链接：传送门
题目需求：Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.(2<=N<=1000000000, 1<=M<=N),
题目解析：
求(X,N),不用想要分解N的因子，分解方法如下，我一开始直接分解for(int i=2;i<=n/2;i++),这样的话如果n==10^9,那么直接超时，因为这点失误直接浪费了一中午
的时间，要这么分解for(int i=2;i*i<=n;i++)具体请在代码里面看，然后开始求（X,N)>=M。
这才是核心：
要求有多少个 i 满足gcd(i, N) = d（1<=i<=N)
如果gcd(i, N) = d，则gcd(i/d, N/d) = 1
由于i <= N，所以 i/d <= N/d，转化为求多少个不大于N/d的数与N/d互质，而这就是欧拉函数
所以有phi(N/d)个 i 满足gcd(i, N) = d，所以求gcd(i,N)>=M,就是求N的因子中大于等于M的欧拉函数值，
即gcd(N/d1)+gcd(N/d2)+...+gcd(N/dn),其中di>=M,且为N的因子。
直接写：（都是15ms，这是后台数据的问题，数据多了肯定还是打表快）
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>typedef __int64 ll;using namespace std;ll n,m,sum,top,key,M,coun,i;int f[1001];int main(){ int T; scanf("%d",&T); while(T--) { sum=1; top=0; scanf("%I64d%I64d",&n,&m); for(i=2; i*i<n; i++) { if(n%i==0) { f[top++]=i; f[top++]=n/i; } } if(i*i==n)//千万别忘了这一句，如16=4*4 { f[top++]=i; } sort(f,f+top); key=-1; for(i=0; i<top; i++) { if(f[i]>=m) { key=i; break; } } if(key==-1) { printf("1\n"); continue; } for(i=key; i<top; i++) { M=n/f[i]; coun=n/f[i]; for(ll z=2; z*z<=M; z++) { if(M%z==0) { coun-=coun/z; M/=z; while(M%z==0) M/=z; } } if(M!=1) coun-=coun/M; sum+=coun; } printf("%I64d\n",sum); } return 0;}
一部分欧拉值打表：
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>typedef __int64 ll;using namespace std;ll n,m,sum,top,key,i;int phi[10006],f[1001];void init(){ memset(phi,0,sizeof(phi)); phi[1]=1; for(int i=2; i<=10000; i++) { if(!phi[i]) { for(int j=i; j<=10000; j=j+i) { if(!phi[j]) phi[j]=j; phi[j]-=phi[j]/i; } } }}int main(){ int T; scanf("%d",&T); init(); while(T--) { sum=1; top=0; scanf("%I64d%I64d",&n,&m); for(i=2; i*i<n; i++) { if(n%i==0) { f[top++]=i; f[top++]=n/i; } } if(i*i==n) { f[top++]=i; } sort(f,f+top); for(i=0; i<top; i++) { if(f[i]>=m) { key=i; break; } } if(key==-1) { printf("1\n"); continue; } for(ll i=key; i<top; i++) { if(n/f[i]<=10000) { sum+=phi[n/f[i]]; continue; } ll M=n/f[i]; ll coun=n/f[i]; for(ll z=2; z*z<=M; z++) { if(M%z==0) { coun-=coun/z; M/=z; while(M%z==0) M/=z; } } if(M!=1) coun-=coun/M; sum+=coun; } printf("%I64d\n",sum); } return 0;}
大神博客：http://hi.baidu.com/bg1995/item/ef25e3261f584053c38d59a8
HDU2588:GCD（欧拉函数的应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。