欧拉函数

发表于 更新于 分类于 Valine： 本文字数： 813 阅读时长 ≈ 1 分钟

上次在讲幂模算法时提到，对于a^b%m，指数b不能令b=b%m使b变小，但是让b=b%phi(m)，其中phi是欧拉函数。

欧拉函数phi(m)的值是模m的缩系的元素个数，小于m的与m互质的自然数构成模m的缩系。

所以phi(m)也是小于等于m并与m互质的自然数的个数。

但是用gcd（最大公约数）来统计与m互质的自然数是比较慢的。

欧拉函数有一个快速算法

1
2
3
4
5
6
7
ll phi(ll n) {
    auto factors = factorize(n);
    for(auto [p, k] : factors) {
        n = n / p * (p-1);
    }
    return n;
}

其中factorize(n)是将n因数分解，返回值是一个vector<pair<ll/*因子p*/, int/*指数k*/>>

n=Πpikin = \Pi p_i ^ {k_i}

相当于对n的每个质因子做了一个操作，除以n的所有的质因子一次，乘以所有(质因子-1)一次，得到的结果就是n的欧拉函数值。

factorize可以用如下实现

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<pair<ll, int>> factorize(ll n) {
    vector<pair<ll, int>> result;
    while(n!=1) {
        ll p = min_divisor(n);
        int c = 0;
        do {
            n/=p;
            ++c;
        } while(n%p==0);
        result.emplace_back(make_pair(p, c));
    }
    return result;
}

其中min_divisor(n)是n的最小因数（显然也一定是质因数）

min_divisor可以通过预处理的方式打质数表然后枚举试除，或者基于Pollard分解算法实现。更多细节参考线性时间复杂度的质数筛法