\(AcWing\) \(874.\) 筛法求欧拉函数
一、题目描述
给定一个正整数 \(n\),求 \(1∼n\) 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 \(n\)。
输出格式
共一行,包含一个整数,表示 \(1∼n\) 中每个数的欧拉函数之和。
数据范围
\(1≤n≤10^6\)
输入样例:
6
输出样例:
12
二、线性筛法求欧拉函数
依托于线性筛法,可以顺带求出欧拉函数值。
(\(1\)) \(phi[1]=1\),\(φ(1)\)被 定义 为\(1\)
对区间内每个数进行分情况讨论:
(\(2\)) 质数
质数\(i\)的欧拉函数值\(phi[i]=i-1\)
比如\(7\),那么\(1-6\)当中有多少个数与\(7\)互质呢?显然\(6\)个都是嘛。
(\(3\)) 非质数
数字\(i\)在被\(primes[j]\)尝试筛的过程中:
(设 \(p_j=primes[j]\),简便下面的书写)
如果\(i\ \% \ p_j = 0\), 那么 \(phi[i * p_j] = phi[i] * p_j\)
证明:
\(\because\) \(i={p_1}^{\alpha_1} * {p_2}^{\alpha_2} * {p_3}^{\alpha_3} * ... *{p_j}^{\alpha_j}*...*{p_k}^{\alpha_k}\) 【算术基本定理】
$phi[i]= i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_j}) $ 【欧拉公式】
\(p_j*i\)分解质数因数的结果,只比\(i\)多分解了一个\(p_j\),而 \(i \ \% \ p_j = 0\) 说明\(i\)中存在\(p_j\)因子,只不过指数增加了\(1\)个。
\(\therefore\) \(p_j * i ={p_1}^{\alpha_1} * {p_2}^{\alpha_2} * {p_3}^{\alpha_3} * ... *{p_j}^{\alpha_j+1}*...*{p_k}^{\alpha_k}\)
通过瞪眼大法观察欧拉公式可知,欧拉公式只与质数因子相关,而与质数因子的幂次无关! 二者的质数因子没有变化,变化的只是某个质数因子的幂次。所以:
$phi[p_j * i] =p_j * i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_j}) = phi[i] * p_j $
证毕
如果\(i\ \% \ p_j > 0\), 那么 \(phi[i * p_j] = phi[i] * (p_j-1)\)
证明:
\(\because\) $i={p_1}^{\alpha_1} * {p_2}^{\alpha_2} * {p_3}^{\alpha_3} * ... *{p_k}^{\alpha_k} $ 【算术基本定理】
\(phi[i]= i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_k})\)【欧拉公式】
\(p_j*i\)分解质数因数的结果,只是比\(i\)多分解了一个\(p_j\),而 \(i \ \% \ p_j>0\) 说明\(i\)中不存在\(p_j\)这个因子,需要写上去。
$p_j * i ={p_1}^{\alpha_1} * {p_2}^{\alpha_2} * {p_3}^{\alpha_3} * ... * {p_k}^{\alpha_k} * {p_j}^{1} $
$\therefore phi[p_j * i]= p_j * i * (1- \frac{1}{p_1}) * (1- \frac{1}{p_2}) * (1- \frac{1}{p_3}) * ... * (1- \frac{1}{p_k}) * (1- \frac{1}{p_j}) $
$\therefore phi[p_j * i]= p_j * phi[i] * (1 - \frac{1}{p_j}) = phi[i] * ( p_j -1) $
证毕
三、实现代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int primes[N];
int cnt;
int phi[N];
int st[N];
int res;
void get_eulers(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
phi[i] = i - 1; // ①质数
}
for (int j = 0; primes[j] <= n / i; j++) {
int t = primes[j] * i;
st[t] = 1;
if (i % primes[j] == 0) {
phi[t] = phi[i] * primes[j]; // ② i%pj==0
break;
} else
phi[t] = phi[i] * (primes[j] - 1); // ③i%pj>0
}
}
}
signed main() {
int n;
cin >> n;
get_eulers(n);
for (int i = 1; i <= n; i++) res += phi[i];
printf("%lld\n", res);
}