题目链接：http://acm.hust.edu.cn/vjudge/contest/125308#problem/G
题目大意，1<=x<=N且gcd(x,n)>=m(gcd是x和n的最小大公因数） 一开始没脑子就想求出所有x和n的公因数在和n比较，然而n很大（10^8）这样做会超时.真是一点懒都不能偷。。看了一下别人的博客，说要用欧拉函数（少于或等于n的数中与n互质的数的数目）
题目思路：求x,n的最大公因数d 即：x=p*d,n=q*d,因为d是最大公因数，所有p,q是互质的，在d>=M的情况下，问有多少个p和q互质,题目就转换成了求q的欧拉函数值 即满足：n=p*d,并且d>=m的p的欧拉函数值之和了
#include<iostream> #include<cstdio> using namespace std; int euler(int n)//欧拉函数的模板 { int res=n,a=n; for(int i=2;i*i<=a;i++) { if(a%i==0) { res=res/i*(i-1);//先除防止溢出 while(a%i==0) a/=i; } } if(a>1) res=res/a*(a-1); return res; } int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int num=0; for(int i=1;i*i<=n;i++) { if(n%i==0) { if(i>=m) num=num+euler(n/i); if(n/i>=m&&i*i!=n)//特判 num=num+euler(i); } } printf("%d ",num); } return 0; }