题目链接：HDU2588
题目大意：给你n，m ，1<i<=n gcd(i,n)>=m 问这样的i 有几个。
代码借鉴：大佬的代码
思路：假设gcd(i,n)=a, 那么n=a*b ,i=a*d (b>=d&&b,d互质)，若b,d不互质，那么最大公约数就不是a了。然后只要让a>=m即可 =>a确定了=>b 就确定了,又因为b>=d&&b,d互质，问题就转换成了求φ（b）即欧拉函数。
那怎么求a 呢，n的范围是1e9,求n的因子 如果遍历整个n，一定会超时，那么我们只要遍历sqrt(n)即可，对于每一个n%i==0 同时考察其 i 和 n/i 这样时间大大缩短。
AC代码
/* HDU2588 欧拉函数应用 2017年8月7日12:29:37 AC */ #include<stdio.h> #include<math.h> int euler(int n){ //返回euler(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,ans; scanf("%d",&t); while(t--){ ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=sqrt(n);i++){ if(n%i==0){ if(i>=m) ans+=euler(n/i); if(n/i>=m&&i!=(n/i)) ans+=euler(i); } } printf("%d\n",ans); } return 0; }
