hdu 2588 GCD-欧拉函数

*题目大意：输入m, n(n < 1000000000),求1~n之间中gcd(x, n) >=m 的x个数。 *解题思路： * 找出N的所有大于等于M的因子(x1,x2,x3.....xi)，然后设k=N/xi； * 下面只需找出小于k且与k互质的数。 * 因为：设y与k互质且小于k，那么gcd（y*xi，k*xi）=xi； * （xi为N的因子，且xi大于等于M）。#include<cstdio> #include<cmath> int euler(int n) //欧拉函数 { int t=n,i,j; for(i=2;i*i<=n;i++) { if(n%i==0) { t=t/i*(i-1); while(n%i==0) n/=i; } } if(n>1) t=t/n*(n-1); return t; } int main() { int n,m,i,j,t,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); ans=0; j=sqrt(n); for(i=1;i<j;i++) { if(n%i) continue; if(i>=m) ans+=euler(n/i); if(n/i>=m) ans+=euler(i); } if(j*j==n&&j>=m) ans+=euler(j); printf("%d\n",ans); } }