1.欧拉函数证明

欧拉函数：对于一个正整数n，在1~n中与n互质的数的个数

对于正整数 $n$ ， $p_{1}, p_{2}, \dots, p_{k}$ 是n的k个质因子

欧拉函数的公式如下：
$p h i (n)$ = $n$ $\times$ (1 - $\frac{1}{p_{1}}$ ) $\times$ (1 - $\frac{1}{p_{2}}$ ) $\times$ $\dots$ $\times$ (1 - $\frac{1}{p_{k}}$ ) ①

那么对于另一种方式：由于唯一分解定理，我们可以考虑将这 $k$ 个质因子的所有倍数筛去，那么得到的结果就是欧拉函数

$p h i (n)$ = $n$ $-$ $\frac{n}{p_{1}}$ $-$ $\frac{n}{p_{2}}$ $-$ $\frac{n}{p_{3}}$ $-$ $\dots$ $-$ $\frac{n}{p_{k}}$ $+$ $\frac{n}{p_{1} * p_{2}}$ $+$ $\dots$ $+$ $\frac{n}{p_{n - 1} * p_{n}}$ $-$ $\frac{n}{奇数个质因子相乘}$ $+$ $\frac{n}{偶数个质因子相乘}$ $\dots$ ②

将①式展开会发现与②式相同，所以得证

2.欧拉线性筛

对于多组询问如果每次都调用欧拉函数则会超时，所以预处理出一部分的欧拉函数就显得很有必要了。

① 对于质数，其欧拉函数为值减 $1$ ，如 $p h i (5) = 5 - 1 = 4$
② 当 $i$ % $p r i [j] = = 0$ , 我们可以发现i中存在 $p r i [j]$ ，因此令 $t$ $= i$ $*$ $p r i [j]$ ,则 $p h i (t) = p h i (i)$ $*$ $p r i [j]$
③ 当 $i$ % $p r i [j]! =$ $0$ ,我们发现i中不存在 $p r i [j]$ ，仍然令 $t$ = $i$ $*$ $p r i [j]$ ,则 $p h i (t)$ = $p h i (i)$ * $p r i [j]$ * ( $1$ $-$ $\frac{1}{p r i [j]}$ )
即 $p h i (t)$ $=$ $p h i (i)$ $*$ ( $p r i [j] - 1$ )

int phi[N];
int pri[N], cnt; bool st[N];
void Euler(int n){
	phi[1] = 1;
	for(int i = 2; i <= n; i++){
		if(!st[i]) {
			pri[cnt++] = i;
			phi[i] = i - 1;
		}
		
		for(int j = 0; j < cnt && i <= n / pri[j]; j++){
			st[i * pri[j]] = true;
			
			if(i % pri[j] == 0) {phi[i * pri[j]] = phi[i] * pri[j]; break;}
			else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
		}
	}
}

欧拉函数证明及欧拉线性筛

1.欧拉函数证明

2.欧拉线性筛