题目大意：给定N,M, 求1<=X<=N 且gcd(X,N)>=M的个数。

题解：首先，我们求出数字N的约数，保存在约数表中，然后，对于大于等于M的约数p[i]，求出Euler(n/p[i])，累计就是答案。因为对于每一个大于等于m的约数，GCD(N,t*p[i])=p[i]>=m（t与p[i]互质），所以n除以p[i]的欧拉函数的和就是答案。

#include <cstdio>int T,cnt,p[10000],n,m,i;int Euler(int n){    int ret=1;    for(int i=2;i*i<=n;i++){        if(n%i==0){            n/=i,ret*=i-1;            while(n%i==0)n/=i,ret*=i;        }    }    if(n>1)ret*=(n-1);    return ret;}int main(){    scanf("%d",&T);    while(T--){        int ans=cnt=0;         scanf("%d%d",&n,&m);        for(i=1;i*i<n;i++)if(n%i==0)p[cnt++]=i,p[cnt++]=n/i;        if(n%i==0)p[cnt++]=i;        for(int i=0;i<cnt;i++)if(p[i]>=m)ans+=Euler(n/p[i]);        printf("%d\n",ans);    }return 0;}

HDU 2588 GCD