欧拉函数

上次在讲幂模算法时提到,对于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分解算法实现。更多细节参考线性时间复杂度的质数筛法