欧拉函数
详细证明请移步大佬区
欧拉函数的简单结论:
$$\phi(N)= N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times (1 - \frac{1}{p_3})··· \times (1 - \frac{1}{p_k})$$
$$(表示从1到N中一共有多少个数字与N互质,p表示N分解出来的质因数)$$
举个小栗子:
Tips:什么是互质? 互质:当两个数的最大公约数仅为 1 时,称这两个数为互质。
栗子: 假设 $N = 6$, 首先将 $6$ 分解质因数,$6 = 2 ^ 1 \times 3 ^ 1 $,接下来套用公式
$$\phi(6) = 6 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 6 \times \frac{1}{2} \times \frac{2}{3} = 2$$
$\therefore$ 在 1 到 6 中与 6 互质的数一共有2个。(分别是 1 和 5)
代码中,因为在公式中$(1 - \frac{1}{a})$很容易出现小数,这是不允许的,所以我们可以变化一下:
$$(1 - \frac{1}{a}) = (\frac{a}{a} - \frac{1}{a}) = \frac{a - 1}{a}$$
$$所以在代码中我们可以先除以 a 再乘上 a - 1$$
短小精悍的AC代码
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while(n -- )
{
int a;
cin >> a;
int res = a;
for(int i = 2; i <= a / i; i ++ )
{
if(a % i == 0)
{
res = res / i * (i - 1);
while(a % i == 0) a /= i;
}
}
if(a > 1) res = res / a * (a - 1);
cout << res << endl;
}
return 0;
}
太强了,厉害