欧拉函数例题汇总

发表于 更新于 分类于
本文字数： 8.1k 阅读时长 ≈ 7 分钟

hdu 1787 GCD Again

Problem Description

Do you have spent some time to think and try to solve those unsolved problem after one ACM contest?
No? Oh, you must do this when you want to become a “Big Cattle”.
Now you will find that this problem is so familiar:
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 I am considering a little more difficult problem:
Given an integer N, please count the number of the integers $ M (0< M < N) $ which satisfies $ (N, M) > 1 $.
This is a simple version of problem “GCD” which you have done in a contest recently,so I name this problem “GCD Again”.If you cannot solve it still,please take a good think about your method of study.Good Luck!

Input

Input contains multiple test cases. Each test case contains an integers $ N (1<N<100000000) $. A test case containing 0 terminates the input and this test case is not to be processed.

Output

For each integers N you should output the number of integers M in one line, and with one line of output for each line in input.

Sample Input

1
2
3
2
4
0

Sample Output

1
2
0
1

思路：

1
求小于n且与n不互质的正整数的个数。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
LL n;
LL get_Euler(LL x){
    LL res = x;
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1LL) res = res / x * (x - 1);
    return res;
}

int main(){
    while(cin >> n && n) {
        cout << n - 1 - get_Euler(n) << endl;
    }
    return 0;
}

hdu 2824 The Euler function

Problem Description

The Euler function phi is an important kind of function in number theory, $ (n) $ represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate $ (a)+ (a+1)+….+ (b) $.

Input

There are several test cases. Each line has two integers $ a, b (2<a<b<3000000) $ .

Output

Output the result of $ (a)+ (a+1)+….+ (b) $.

Sample Input

1
3 100

Sample Output

1
3042

思路：

打表求欧拉函数值前缀和，注意只需开一个数组就够了，避免超内存。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const LL maxn = 3e6+5;
LL a, b, phi[maxn];
void phi_table() {
    phi[0] = 0LL, phi[1] = 1LL; //1的欧拉函数值为1，唯一与1互质的数
    for(LL i = 2; i < maxn; ++i) phi[i] = i; //先初始化为其本身
    for(LL i = 2; i < maxn; ++i) {
        if(phi[i] == i) { //如果欧拉函数值仍为其本身，说明i为素数
            for(LL j = i; j < maxn; j += i) //把i的欧拉函数值改变，同时也把能被素因子i整除的数的欧拉函数值改变
                phi[j] = phi[j] / i * (i - 1);
        }
    }
    for(LL i = 2LL; i < maxn; ++i) phi[i] += phi[i - 1];
}
int main(){
    phi_table(); //预处理打表
    while(cin >> a >> b) {
        cout << phi[b] - phi[a - 1] << endl;
    }
    return 0;
}

hdu 3501 Calculation 2

Problem Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Input

For each test case, there is a line containing a positive integer $ N(1 ≤ N ≤ 1000000000) $. A line containing a single 0 follows the last test case.

Output

For each test case, you should print the sum module 1000000007 in a line.

Sample Input

1
2
3
3
4
0

Sample Output

1
2
0
2

思路：

求小于n且与n不互质的所有正整数之和，公式：$ [\frac{n(n - 1)}{2} - \frac{n*\varphi(n)}{2}] mod \; 1000000007 $.

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
const LL mod = 1000000007;
LL n;
LL get_Euler(LL x){
    LL res = x; //初始值
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1); //先除后乘，避免数据过大
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1LL) res = res / x * (x - 1); //若x大于1，则剩下的x必为素因子
    return res;
}

int main(){
    while(cin >> n && n) {
        cout << (n * (n - 1) / 2 - n * get_Euler(n) / 2) % mod << endl; 
    }
    return 0;
}

hdu 2588 GCD

Problem 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 \leq X \leq N $ and $ (X, N) \geq M $.

Input

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

Output

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

Sample Input

1
2
3
4
3
1 1
10 2
10000 72

Sample Output

1
2
3
1
6
260

思路：

$ \because GCD(X, N) \geq M, X \in [1,N], \therefore GCD(X, N) $ 一定是N的约数。假设我们已经知道N的一个约数为 $ P(P \geq M) $，则问题转换成在 $ [1,N] $ 内有多少个数X，满足$ GCD(X, N) = P $ (假设P是一个已知值)，接下来就是枚举每个 $ P(P \geq M) $，累加每个P对应X的个数。但是对于每个不小于M的N的约数P去计算满足$ GCD(X, N) \geq M $ 的X的个数的情况可能比较复杂，需要考虑的情况比较多，简单的想法是：在 $ [1,N] $内用 $ O(NlogN) $ 的时间复杂度判断一下 $ GCD(X, N) $ 是否不小于M，但是题目中N最大为$ 10^{10} $，这肯定是超时的了。
因此进一步推导：$ \because GCD(X, N) = P, \therefore GCD(\frac{X}{P}, \frac{N}{P}) = 1 $（很明显 $ \frac{X}{P} $ 与 $ \frac{N}{P} $ 互质），又 $\because X \leq N $，$\therefore \frac{X}{P} \leq \frac{N}{P} $，而问题是求X的个数，结合欧拉函数的定义可知即求小于 $ \frac{N}{P} $ 且与其互质的正整数 $ \frac{X}{P} $ 的个数，即求 $ \varphi(\frac{N}{P}) $。对于N的每个约数P，我们只需从1枚举到 $ \sqrt{N} $ 即可，因为 $ \frac{N}{P} $ 可以得到N的另一个约数（相当于枚举了N的所有约数），这样时间复杂度就大大降低了。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
const LL mod = 1000000007;
int T; LL n, m, ans;
LL get_Euler(LL x){
    LL res = x; //初始值
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1); //先除后乘，避免数据过大
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1LL) res = res / x * (x - 1); //若x大于1，则剩下的x必为素因子
    return res;
}

int main(){
    while(cin >> T) {
        while(T--) {
            cin >> n >> m; ans = 0LL;
            for(LL i = 1LL; i * i <= n; ++i) {
                if(n % i) continue; //跳过不是n的约数
                if(i >= m && i * i != n) ans += get_Euler(n / i); //约数i不小于m，累加phi[n/i]，如果i*i==n，只算一次即可
                if(n / i >= m) ans += get_Euler(i); //另一个约数n/i不小于m，累加phi[n/(n/i)]=phi[i]
            }
            cout << ans << endl;
        }
    }
    return 0;
}

poj 2480 Longge’s problem

Description

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer $ N(1 < N < 2^{31}) $,you are to calculate . “Oh, I know, I know!” Longge shouts! But do you know? Please solve it.

Input

Input contain several test case. A number N per line.

Output

For each N, output , a line

Sample Input

1
2
2
6

Sample Output

1
2
3
15

思路1：

给出一个数n，求 $ 1-n $ 这n个数与n的最大公约数之和。举个栗子：当$ n = 4 $ 时，1，2，3，4与4的最大公约数分别为1，2，1，4，累加和为8。正解：$ 1-n $ 中每个数与n的最大公约数肯定是n的一个因子，所以我们只需要枚举n的每一个因子 $ x \in [1, \sqrt{n}] $ ，然后看有多少个满足 $ gcd(k, n) == x $，即求满足 $ gcd(\frac{k}{x}, \frac{n}{x}) == 1 $ 中k的个数（用欧拉函数求解），则公式为：。

AC代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1e6+5;
LL n, ans;
LL get_Euler(LL x){
    LL res = x;
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1LL) res = res / x * (x - 1);
    return res;
}

int main(){
    while(cin >> n) {
        ans = 0LL;
        for (LL i = 1LL; i * i <= n; ++i) {
            if(n % i == 0) {
                ans += i * get_Euler(n / i);
                if(i * i != n) ans += n / i * get_Euler(i);
            }
         }
         cout << ans << endl;
    }
    return 0;
}

思路2：

思路和上面相同，， 将问题求解转换一下 ，其中 即求 ，
化简公式得 ，
再根据积性函数的性质得 。时间复杂度是 。

AC代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
LL n;
LL solve(LL x) {
    LL p_i, k, ans = 1LL;
    for(LL i = 2LL; i * i <= x; ++i) {
        if(x % i == 0) {
            p_i = 1LL, k = 0; 
            while(x % i == 0) {k++, p_i *= i, x /= i;}
            ans *= (k + 1) * p_i - k * p_i / i; //(k+1)*p^k - k*p^(k-1)
        }
    }
    if(x > 1LL) ans *= 2 * x - 1LL; 
    return ans;
}
int main() {
    while(cin >> n) {
        cout << solve(n) << endl;
    }
    return 0;
}
0%