hdu 2588 GCD (歐拉函數）

題目：https://cn.vjudge.net/problem/HDU-2588

gcd（x,n）>=m，設gcd（x,n）=i，

是以有 i * a=x，i *b =n ；保證 i >=m,枚舉 i 即可。

但是資料太大，我們可以枚舉符合條件的小于sqrt(n)的 i 即可，同時把 n / i 枚舉出來

那麼為什麼 歐拉（b）就是我們要的呢？因為 歐拉（b），得到了a的數量，也就是（a，b）的對數，也就是（x，n）的對數。

由x<=n,則a<=b;

比如：10 2

   b    n              i

【2,10】 2

【4,10】  2

【5,10】 5

【6,10】 2

【8,10】 2

【10,10】 10

枚舉 i=2時，eular（10/2）=4

接下來eular（10/5）=1 ，eular（10/10）=1

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll eular(ll n){   //注意傳的是ll
    ll i,j,ans=n;
    for(i=2;i*i<=n;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 main(){
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        ll ans=0;
        for(int i=1;i*i<=n;i++){
            if(n%i==0){//i是gcd（x,n）,n%i當然要等于0
                if(i>=m)  ans+=eular(n/i);
                if(i*i!=n && n/i>=m) ans+=eular(i);  //n為完全平方數時，i在上個if已經枚舉過了。
            }                                        //這裡其實是eular（n/（n/i））
        }
        printf("%lld\n",ans);
    }
    return 0;
}