HDU 2588-GCD(欧拉函数)-白红宇

HDU 2588-GCD(欧拉函数)

阅读量：2029 次

发布时间：2019-04-28

本文共 1020 字，大约阅读时间需要 3 分钟。

题目地址：

题意：给两个数n,m(2<=n<=1000000000, 1<=m<=n), 求1<=x<=n 且gcd(x,n)>=m的个数x的个数。

思路：因为x要满足1<=x<=n 且gcd(x,n)>=m，所以x为n的因子，即gcd(x,n)=x>=m，设y=n/x，则y的欧拉函数为小于y且与y互质的数的个数。假设与y互质的数为p1,p2,p3……，那么gcd(x*pi,n)=x>=m.即要找出所有符合要求的y的欧拉函数值的和即可。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;using namespace std;int Euler(int n){ int m=floor(sqrt(n+0.5)); int ans=n; for(int i=2;i<=m;i++){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0) n/=i; } } if(n>1) ans=ans/n*(n-1); return ans;}int Solve(int n,int m){ int cnt=0; for(int i=1;i*i<=n;i++){ //分解出质因子 if(n%i==0){ //分解质因子 if(i>=m) cnt+=Euler(n/i); if((n/i)!=i&&(n/i)>=m)//判断是否为平方数 cnt+=Euler(i); } } return cnt;}int main(){ int T,n,m; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&m); printf("%d\n",Solve(n,m)); } return 0;}

转载地址：http://djsaf.baihongyu.com/

你可能感兴趣的文章

Linux多线程编程的时候如何查看一个进程中的某个线程是否存活