欧拉函数

coding>C++
944 词

题目描述

给定一个大于1，不超过2000000的正整数n，输出欧拉函数，\phi(n)的值。
如果你并不了解欧拉函数，那么请参阅提示。

输入

在给定的输入文件中进行读入： 
一行一个正整数n。 

输出

将输出信息输出到指定的文件中: 一行一个整数表示\phi(n)。

样例输入

17

样例输出

16

提示

欧拉函数\phi(n)是数论中非常重要的一个函数，其表示1到n之间，与n互质的数的个数。显然的，我们可以通过定义直接计算\phi(n)。 当然，\phi(n)还有这么一种计算方法。 首先我们对n进行质因数分解，不妨设n={p_1}^{a_1} * {p_2}^{a_2} * … *{p_k}^{a_k} （这里a^b表示a的b次幂，p_1到p_k为k个互不相同的质数，a_1到a_k均为正整数），那么 \phi(n)=n(1-(1/p_1))(1-(1/p_2))….(1-(1/p_k)) 稍稍化简一下就是 \phi(n)=n(p_1-1)(p_2-1)…(p_k-1)/(p_1*p_2*…*p_k) 计算的时候小心中间计算结果超过int类型上界，可通过调整公式各项的计算顺序避免(比如先做除法)!

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
#include <iostream>
#include <cmath>
using namespace std;
const int Maxn = 2000000;
int phi[Maxn];
void Euler(int n) {
    for (int i = 2; i <= n; i++)
        phi[i] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!phi[i]) {
            for (int j = i; j <= n; j += i) {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}
int main() {
    Euler(Maxn);
    int n;
    cin >> n;
    cout << phi[n] << endl;
    return 0;
}