hdu 2588 GCD(欧拉函数)

Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6. (a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem: Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

Output

For each test case,output the answer on a single line.

Sample Input

3
1 1
10 2
10000 72

Sample Output

1
6
260
解题思路:∵GCD(X,N)>=M,X∈[1,N],∴GCD(X,N)一定是N的约数。假设我们已经知道N的一个约数为P(P>=M),则问题转换成在[1,N]内有多少个数X,满足GCD(X,N)=P(P假设是一个已知值),接下来就是枚举每个P(P>=M),累加每个P对应X的个数。但是对于每个不小于M的N的约数P去计算满足GCD(X,N)>=M的X的个数的情况可能比较复杂,需要考虑的情况比较多,简单的想法是:在[1,N]内用O(NlogN)的时间复杂度判断一下GCD(X,N)是否不小于M,但是题目中N最大为10^10,这肯定是超时的了。因此进一步推导:∵GCD(X,N)=P,∴GCD(X/P,N/P)=1(很明显X/P与N/P互质),又∵X<=N,∴X/P<=N/P,而问题是求X的个数,结合欧拉函数的定义可知即求不大于N/P且与其互质的数X/P的个数,即求ϕ(N/P)。对于N的每个约数P,我们只需从1枚举到根号N,因为N/P可得N的另一个约数(相当于枚举了N的所有约数),这样时间复杂度就大大降低了。
AC代码:
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #include <vector>
 6 #include <set>
 7 using namespace std;
 8 typedef long long LL;
 9 const int maxn = 1e6+5;
10 const LL mod = 1000000007;
11 int T; LL n, m, ans;
12 LL get_Euler(LL x){
13     LL res = x; ///初始值
14     for(LL i = 2LL; i * i <= x; ++i) {
15         if(x % i == 0) {
16             res = res / i * (i - 1); ///先除后乘,避免数据过大
17             while(x % i == 0) x /= i;
18         }
19     }
20     if(x > 1LL) res = res / x * (x - 1); ///若x大于1,则剩下的x必为素因子
21     return res;
22 }
23 
24 int main(){
25     while(cin >> T) {
26         while(T--) {
27             cin >> n >> m; ans = 0LL;
28             for(LL i = 1LL; i * i <= n; ++i) {
29                 if(n % i) continue; ///跳过不是n的约数
30                 if(i >= m && i * i != n) ans += get_Euler(n / i); ///约数i不小于m,累加phi[n/i],如果i*i==n,只算一次即可
31                 if(n / i >= m) ans += get_Euler(i); ///另一个约数n/i不小于m,累加phi[n/(n/i)]=phi[i]
32             }
33             cout << ans << endl;
34         }
35     }
36     return 0;
37 }

原文地址:https://www.cnblogs.com/acgoto/p/9424944.html