题目链接：https://vjudge.net/contest/125308#problem/G
题意：求有多少x(1<=x<=n),使得gcd(x,n)>=m; 先求n的所有大于等于m的因子, 刚开始用了模拟，超时，看了下往上的题解，说要用到欧拉函数求解，就看了下欧拉函数， ans=∑phi[n/ei];phi[i]为欧拉函数，为不大于i且与i互质的正整数个数 对于一个与ei互质且小于等于n/ei的正整数p来说，p*ei<=n,gcd(p*ei,n)=ei;则phi[n/ei]就是1~n中的与n最大公约数是ei的个数。而n与1~n的最大公约数必定是n的因子。 所以符合gcd(x,n)>=m的x为n所有大于等于m因子的倍数，用phi即可避免重复。
那么此题就很容易解了
AC代码:
#include <stdio.h>
#define size 1000000
int a[size]; int P( int n )
{
int ans = n;
for( int i = ; i*i <= n ; i++ )
{
if( n%i== )
{
ans = ans / i * (i-);
while( n%i== )
n /= i;
}
}
if(n>)
ans = ans / n * (n-);
return ans;
} int main()
{ int t , n , m , t1 , ans;
scanf("%d",&t);
while( t-- )
{
scanf("%d%d",&n,&m);
t1 = ans = ;
for( int i = ; i*i<=n ; i++ )
{
if( n%i == )
{
if(i*i==n)
a[t1++] = i;
else
{
a[t1++] = i;
a[t1++] = n/i;
}
}
}
for( int i = ; i<t1 ; i++ )
{
if( a[i]>=m )
{
ans += P( n/a[i] );
}
}
printf("%d\n",ans);
}
return ;
}