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;
}