题目问[1,n]中与n的gcd大于等于m的数的个数。
好难想。。。
假设x满足条件，那么gcd(x,n)=d>=m，而x/d与n/d一定互质。
又x<=n，所以x/d<=n/d。
于是gcd(x,n)=d的x个数就等于小于n/d且与n/d互质的个数，即phi(n/d)。
不同的d对应的x肯定会不重复，因为它们与n的gcd本来就不同。那么就是枚举最大公约数d，累加phi(n/d)就是答案了。
#include<cstdio>
#include<cstring>
using namespace std;
int phi(int x){
int y=x;
for(int i=; i*i<=x; ++i){
if(x%i) continue;
while(x%i==) x/=i;
y-=y/i;
}
if(x!=) y-=y/x;
return y;
}
int main(){
int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
int res=;
for(int i=; i*i<=n; ++i){
if(n%i) continue;
int j=n/i;
if(i>=m) res+=phi(j);
if(i!=j && j>=m) res+=phi(i);
}
printf("%d\n",res);
}
return ;
}