首页 > 代码库 > HDU 2588 GCD
HDU 2588 GCD
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2588
解题思路:
本来的思路是枚举大于等于M的数S,若S|N,那么KS(KS<N)GCD(KS,N)>=M,
这样有重复的。
而这样有重复的:
若GCD(x,N)>=M.
设y=N/C,那么y的素因子有phi[i],phi[i+1].......,
那么GCD(x*phi[i],N)>=M,
而根据算术基本定理可知上述方法没有重复的。
那么ans=所有大于M的N的因子X的N/X的欧拉函数值
实现代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 8 long long euler(long long n){ 9 long long res=n; 10 for(int i=2;i*i<=n;i++){ 11 if(n%i==0){ 12 res=res/i*(i-1); 13 while(n%i==0) 14 n/=i; 15 } 16 } 17 if(n>1) //剩下的数也是n的素因数 18 res=res/n*(n-1); 19 return res; 20 } 21 22 23 int solve(int N,int M){ 24 long long ans=0;
//用这种方法超时。 25 /*for(int i=M;i<=N;i++){ 26 if(N%i==0) 27 ans+=euler(N/i); 28 }*/ 29 for(int i=1;i*i<=N;i++){ 30 if(N%i==0){ 31 if(i>=M) 32 ans+=euler(N/i); 33 if((N/i)!=i&&N/i>=M) 34 ans+=euler(i); 35 } 36 37 } 38 cout<<ans<<endl; 39 } 40 41 int main(){ 42 int T; 43 scanf("%d",&T); 44 while(T--){ 45 int N,M; 46 cin>>N>>M; 47 solve(N,M); 48 } 49 return 0; 50 }
HDU 2588 GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。