题意：给出两个数N,M(N≥M)，有1≤x≤N，求gcd（N，x）≥M的x的数目。
思路：设a=gcd（N，x）且a≥M。则这个gcd可变化为gcd（N/a,x/a）=1，并求出x/a的数目，可以发现：x/a和N/a是互质的，这不就是等价于求N/a的欧拉函数吗？最后特判一下i*i==n的情况即可。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<map> #include<queue> #include<vector> #include<string> #define ll long long #define PI acos(-1.0) #define F first #define S second #define pb push_back #define debug(x); printf("debug%d ",x); #define des(x); printf("des:%s ",x+1); const ll INF=0x3f3f3f3f3f3f3f3f; const int inf=0x3f3f3f3f; const ll mod=1e9+7; using namespace std; int t; ll n,m; const int N=1e5+5; ll oula(ll n) { if(n==1) return 1; ll ans=n; for(ll i=2;i*i<=n;i++) { if(n%i==0) { ans=ans-ans/i; while(n%i==0) { n/=i; } } } if(n!=1) { ans=ans-ans/n; } return ans; } int main() { scanf("%d",&t); while(t--) { scanf("%lld%lld",&n,&m); if(n==m) { printf("1 "); } else { ll ans=0ll; for(ll i=1;i*i<=n;i++) { if(n%i==0) { if(i>=m) { ans+=oula(n/i); } if(n/i>=m&&i*i!=n) { ans+=oula(i); } } } printf("%lld ",ans); } } return 0; }