SGU 102 - Coprimes

Description

For given integer NN (1N1041\leq N\leq 10^4) find amount of positive numbers not greater than NN that coprime with NN. Let us call two positive integers (say, AA and BB, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. AA and BB are coprime iff gcd(A,B)=1\mathrm{gcd}\left(A,B\right) = 1).

Input

Input file contains integer NN.

Output

Write answer in output file.

Sample Input

1
9

Sample Output

1
6

Analysis

我首先想到的是欧拉函数 φ(N)\varphi\left(N\right),后来发现数据量并不是特别的大,所以又用暴力做了一遍,也 AC 了。

这道题目的重点在于欧拉函数 φ(N)\varphi\left(N\right) 的求法,现总结如下:

欧拉函数 φ(N)\varphi\left(N\right):小于等于 NN 且与 NN 互素的正整数的个数。

欧拉函数据有如下性质:

  • φ(1)=1\varphi\left(1\right) = 1
  • φ(N)=NpN(p1p)\varphi\left(N\right) = N\cdot\sum_{p|N}{\left(\frac{p-1}{p}\right)},其中 pp 为素数
  • φ(pk)=pkpk1=(p1)pk1\varphi\left(p^k\right) = p^k - p^{k - 1} = \left(p-1\right)p^{k - 1},其中p为素数
  • φ(mn)=φ(m)φ(n)\varphi\left(mn\right)=\varphi\left(m\right)\cdot \varphi\left(n\right),其中 gcd(m,n)=1\mathrm{gcd}\left(m,n\right)=1

根据第 2 个式子我们就可以求出欧拉函数。

基本思路:首先置 φ(N)=N\varphi\left(N\right) = N,然后枚举 NN 的素因子 pp,将 pp 的整数倍的欧拉函数 φ(kp)\varphi\left(k\cdot p\right)φ(kp)=φ(kp)p1p\varphi\left(k\cdot p\right) = \varphi\left(k\cdot p\right) \cdot \frac{p - 1}{p} 即可。

基本代码如下:

 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
38
39
40
41
42
#include <iostream>
 
using namespace std;
 
const int MAX = 1024;
 
int N;
int p[MAX], phi[MAX];
 
int main()
{
    cin >> N;
    for(int i = 1; i <= N; i++)  // 初始化
    { p[i] = 1; phi[i] = i; }
    p[1] = 0;   // 1不是素数
    for(int i = 2; i <= N; i++)  // 筛素数
    {
        if(p[i])
        {
            for(int j = i * i; j <= N; j += i)
            { p[j] = 0; }
        }
    }
    for(int i = 2; i <= N; i++)  // 求欧拉函数
    {
        if(p[i])
        {
            for(int j = i; j <= N; j += i)   // 处理素因子p[i]
            {
                phi[j] = phi[j] / i * (i - 1);  // 先除后乘,防止中间过程超出范围
            }
        }
    }
    cout << "Primes: " << endl;
    for(int i = 1; i <= N; i++)
    { if(p[i]) { cout << i << " "; } }
    cout << endl;
    cout << "Euler Phi Function: " << endl;
    for(int i = 1; i <= N; i++)
    { cout << phi[i] << " "; }
    return 0;
}

Solution

欧拉函数

 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
#include <iostream>
#include <math.h>
#include <stdio.h>
 
using namespace std;
 
int phi(int x);
 
int main()
{
    int N;
    cin >> N;
    cout << phi(N) << endl;
    cout << endl;
    return 0;
}
 
int phi(int x)
{
    int nRet = x;
    int nTmp = (int)sqrt(x);
    for(int i = 2; i <= nTmp; i++)
    {
        if(x % i == 0)
        {
            nRet = nRet / i * (i - 1);
            while(x % i == 0)
            { x /= i; }
        }
    }
    if(x > 1)
    {
        nRet = nRet / x * (x - 1);
    }
    return nRet;
}

暴力

 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
#include <iostream>
#include <math.h>
#include <stdio.h>
 
using namespace std;
 
int gcd(int x, int y);
 
int main()
{
    int N, nRet = 0;
    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        if(gcd(N, i) == 1)
        { nRet++; }
    }
    cout << nRet << endl;
    return 0;
}
 
int gcd(int x, int y)
{
    if(y == 0) { return x; }
    return gcd(y, x % y);
}

SGU 不愧是经典题目的合集,每做一道题都会学到一些新的东西。

使用 Hugo 构建
主题 StackJimmy 设计