题目梗概

T组数据，每组数据输入n,m,问有多少个x满足1<=X<=N 和 gcd (X,N)>=M

 

思考

我们假设S= gcd(X,N) 

那么一定存在a,b使得X=Sa N=Sb  且gcd(a,b)=1

因为 X<=N 即 Sa<=Sb 所以 a<=b 

求X的个数即是求a的个数

求a的个数即是求  b的欧拉函数（比b小且与b互质的数的个数）

但是如果 直接枚举s来计算b 一定会TLE，所以我们需要再深入思考。

我们发现枚举S从1-N有一半的次数是浪费掉的，举个例子 N=8 我枚举S为2 计算b=4 到后面我枚举S为2 计算b=2。

所以在S!=b的情况下 我们只需要枚举计算S的同时，再计算一下b.

 

#include 
     
      #include 
      
       using namespace std;typedef long long ll;ll Euler(ll n){    ll res = n;    for(ll i = 2; i*i <= n;i++){        if(n%i==0) res = res/i*(i-1);        while(n%i==0) n/=i;    }    if(n>1) res = res / n * (n-1);    return res;}int main(){    ll T,n,m,ans;    scanf("%lld",&T);    while(T--){        ans=0;        scanf("%lld%lld",&n,&m);        for(int i=1;i*i<=n;i++){            if(n%i==0){                if(i>=m) ans += Euler(n/i);                if(i*i!=n && n/i>=m) ans+=Euler(i);            }        }        printf("%lld\n",ans);    }    return 0;}