Appearance
若无特殊说明,本章涉及的变量皆为正整数。
定义
性质
质数的欧拉函数
证
的欧拉函数
证
在
通项公式
证
若
根据定义,
积性函数
证
设
设
由
定理
欧拉定理
若
证
费马小定理
若
扩展欧拉定理
若
模板
欧拉函数
cpp
int varphi(int n) {
int ans = n;
for (int i = 2; i <= sqrt(n); i ++) {
if (n % i == 0) {
ans = ans / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if (n > 1)
ans = ans / n * (n - 1);
return ans;
}
线性欧拉算法
求
的欧拉函数。
对质数的 线性筛法 加以改造。
- 若
为质数,则 ; - 利用
和 生成合数时,利用 积性函数 性质:
时间复杂度为
cpp
const int N = 1e6;
int phi[N];
vector<int> prime;
void varphi(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i ++) {
if (!phi[i])
phi[i] = i - 1, prime.push_back(i);
for (int j = 0; j < prime.size(); j ++) {
if (i * prime[j] > n) break;
phi[i * prime[j]] = phi[i] * phi[prime[j]]; // 积性函数
if (i % prime[j] == 0) break;
}
}
}