欧拉函数

欧拉函数定义：

$1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\phi(N)$。
若在算数基本定理中，$N= p_1^{\smash{a_1}} p_2^{\smash{a_2}} \dots p_m^{\smash{a_m}}$，则：
$\phi(N) = N\times {p_1-1 \over p_1}\times{p_2-1 \over p_2}\times \dots \times{p_m-1 \over p_m}$

也可以写作：$\phi(N) = N\times(1-{1 \over p_1})\times(1-{1 \over p_2})\times \dots \times(1-{1 \over p_m})$

什么是互质？

公约数只有1的两个数

比如求得6的欧拉函数：$ϕ(6) = 2$

$1\sim6$满足条件的2个数： $1， 5$，所以等于$2$

再来用公式求一下：

$6 = 2^{\smash{1}} \times 3^{\smash{1}}$

$\phi(6) = 6\times(1- {1 \over 2} )\times (1-{1 \over 3})=2$

证明：

为什么$\phi(N) = N\times(1-{1 \over p_1})\times(1-{1 \over p_2})\times \dots \times(1-{1 \over p_m})$是正确的呢

如何求上图的面积呢？

我们只需要这样： S = (①+②+③)-(①$\cap$②-②$\cap$③-①$\cap$③)+①$\cap$② $\cap$③

因为 ④ 这个面积被减去了三次，所以我们最后还得加一次。

然后再看这个证明~

我们要求$1\sim N$ 中与 $N$ 互质的数的个数

1.我只需要从$1\sim N$中去掉$p_1,p_2,\dots,p_k$ 的所有倍数：

$N=N-{N \over p_1}-{N \over p_2} \dots -{N \over p_k}$

2.但是在去除的过程中，$(p_1, p_2)$或$(p_2, p_3)$可能有相同的倍数，一直到 $(p_i, p_j)$都会重复的去掉一些个数，比如$\phi(6)$，$p_1=2, p_2 = 3$,那么$2, 3$的倍数都有 $6$，$6$被重复去掉了2次，则在需要加回来：

$N=N-{N \over p_1}-{N \over p_2} \dots -{N \over p_k}$

$\space\space\space\space\space\space\space +{N \over p_1p_2} + {N \over p_2p_3}+\dots$

3.同理在加的过程中，重复的加去了一些数的个数，则需要减去：

然后就这样疯狂套娃，如果将$\phi(N) = N\times(1-{1 \over p_1})\times(1-{1 \over p_2})\times \dots \times(1-{1 \over p_m})$展开，就会发现这两个式子是相等的，不太明白的可以搜一下容斥原理。

题目：https://www.acwing.com/problem/content/875/

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
	int n; 
	cin >> n;
	while(n --)
	{
		int x;
		cin >> x;
		int res = x;
		for (int i = 2; i <= x / i; i++)
			if (x % i == 0)
			{
				// 防止越界，res*(1 - 1/i)
				res = res / i * (i - 1);
				while(x % i == 0) x /= i;
			}
		if (x > 1) res = res /x* (x - 1);
		cout << res << endl;
	}
	
	return 0;
}