一文读懂欧拉函数

查看原文

其他

一文读懂欧拉函数

算法数学之美 2019-05-24

算法数学之美

日期：2019年1月22日

正文共：1267字3图

预计阅读时间：4分钟

来源：算数学苑

欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。又称φ函数、欧拉商数。

下面介绍欧拉函数的几个性质：

我们根据这几个性质就可以求出欧拉函数。

基本思路是首先置φ(N)=N，然后再枚举素数p，将p的整数倍的欧拉函数φ(kp)进行如下操作。

代码如下：

#include
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;
}

以上是关于欧拉函数的求法，对于它的应用，这里暂且介绍一个——求解原根的个数。

对于原根的定义，我们可以这样来叙述：

若存在一个实数a，使得( a^i ) mod N,a∈{1,2,3,⋯,N}的结果各不相同，我们就成实数a为N的一个原根。

原根的个数等于φ(φ(N))。这样我们就可以很方便的求出原根的个数。

代码如下：

#include
#include
using namespace std;
typedef unsigned long long ull;
ull N;
ull phi(ull x);
int main()
{
    cin >> N;
    cout << phi(phi(N)) << endl;
    return 0;
}
ull phi(ull x)
{
    ull ans = x;
    ull m = (ull)sqrt(x);
    for(ull i = 2; i <<= m; i++)
    {
        if(x % i == 0)// 求素因子
        {
            ans = ans / i * (i - 1);// 运用通项求解欧拉函数
            while(x % i == 0)// 每个素因子只计算一次
            { x /= i; }
        }
    }
    if(x > 1)// 防质数
    { ans = ans / x * (x - 1); }
    return ans;
}