HDU 2588 数论 欧拉函数

题目链接

题意很简单，思路却有点难想。

从已知条件一步步来分析：
因 GCD（X，N）>=M 而 1<=X<=N

可得出结论1，也是该题重要的突破口：
GCD（X，N）一定是N的约数

这个条件可以给我们一定启发，因为 N 的约数一定是很有限的，我们可不可以枚举N的约数 P （随便给的名字= =），且 P>=M 呢？

假设我们已经得到了这样一个 P ，这时问题转化为：
<==> 求【1，N】中有多少个数X，满足 GCD（X，N）=P （P为一个已知的数）

想到这里，解法其实离我们已经很近了。

枚举X的复杂度是 O（N），我们还有没有更好的解法呢？
假设当前有一个满足条件的X，让我们来考虑他的性质：
一.因为 GCD（X，N） = P的，所以 X/P 一定与 N/P 互质（结论很显然）
二.因为 X<=N ，故 （X/P）<=（N/P） 一定成立

由这两条性质 再结合欧拉函数的定义，很显然：
求X的个数 <==> 求 不大于N/P且与其互质的 X/P的个数 即求 ϕ(N/P)

听说还有容斥的做法 但现在没有一点思路，如果以后懂了再补上（占坑
好像又乱立了一个flag
代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

ll euler(ll x){
    ll res = x;
for(int i=2 ;i*i<=x ;i++){
if(x%i == 0){
            res = res/i*(i-1);
while(x%i==0) x/=i;
        }
    }
if(x>1) res = res/x*(x-1);
return res;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
        ll n,m;
scanf("%I64d%I64d",&n,&m);

        ll ans = 0;
for(ll i=1 ;i*i<=n ;i++){
if(n%i == 0){
if(i >= m){
                    ans += euler(n/i);
                }
if((n/i)>=m && n/i != i){
                    ans += euler(i);
                }
            }
        }
printf("%I64d\n",ans);
    }
return 0;
}