Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3608 Accepted Submission(s): 1954
求 1~N 的范围内存在多少个 X 使得 GCD( X, N ) >= M;
设 s = GCD( X, N);
可知： s >= M,
且存在 a, b 使得 s*a = X, s*b = N, GCD( a, b ) = 1;
因为 X <= N 所以 a <= b;
综上所述：
N 1e9 的范围缩小一半枚举 s ,求得 b；（因为可以同时求得 i 和 N/i 的方案数）
即求满足 GCD（a, b) = 1 且 a <= b 的 a 的个数。
AC code:
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define LL long long 4 using namespace std; 5 6 const int MAXN = 1e9+10; 7 LL N, M; 8 9 LL Euler(LL n) 10 { 11 LL res = n; 12 for(LL i = 2; i*i <= n; i++){ 13 if(n%i == 0) res = res/i*(i-1); 14 while(n%i == 0) n/=i; 15 } 16 if(n > 1) res = res/n*(n-1); 17 return res; 18 } 19 20 int main() 21 { 22 int T_case; 23 scanf("%d", &T_case); 24 LL ans, b; 25 while(T_case--){ 26 scanf("%lld %lld", &N, &M); 27 ans = 0; 28 for(LL s = 1; s*s <= N; s++){ 29 if(N%s) continue; 30 if(s >= M) ans+=Euler(N/s); 31 if(s*s != N && N/s >= M) ans+=Euler(s); 32 } 33 printf("%lld\n", ans); 34 } 35 return 0; 36 }
原文：https://www.cnblogs.com/ymzjj/p/10346998.html
