程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2588 GCD(歐拉函數)

hdu2588 GCD(歐拉函數)

編輯:C++入門知識

hdu2588 GCD(歐拉函數)


題意:求解小於n的數i且gcd(i,n)大於m的i的個數

分析:

對於所有小於n的最大公約數值一定是n的因子,所以,從這個方面下手找i為n的因子且i>m時求解車i的素數倍數且小於n的個數累加起來就好了。以為這個倍數最大為n/i所以求得n/i的歐拉函數值累加起來就好了。

代碼如下:

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
long long euler(long long  n){ //返回euler(n)
     long long  res=n,a=n;
     for(long long  i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先進行除法是為了防止中間數據的溢出
             while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}
//歐拉函數值
long long a[1000010];
int main(){
    long long n,m;
    int t;
    cin>>t;
    while(t--){
        long long ans=0;
        scanf("%I64d%I64d",&n,&m);
        for(int i=1;i*i<=n;i++){//判斷sqrt(n)就好
            if(n%i!=0)continue;
            if(i>=m&&i*i!=n){
                ans+=euler(n/i);
            }
            if(n/i>=m){
                ans+=euler(i);//一個是i,一個是n/i
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved