欧拉函数 $\varphi(n)$ 是定义在正整数 $n$ 上的函数,表示小于或等于 $n$ 的正整数中与 $n$ 互质的数的个数。下面我们来推导欧拉函数的性质及其计算公式。
欧拉函数的性质
-
若 $n$ 是质数 $p$,则 $\varphi(p) = p - 1$。
这是因为除了 $1$ 以外,其他所有小于 $p$ 的正整数都与 $p$ 互质。 -
若 $n = p^k$,其中 $p$ 是质数,则 $\varphi(p^k) = p^k - p^{k-1}$。
这是因为小于 $p^k$ 的正整数中,能被 $p$ 整除的数有 $p^{k-1}$ 个(即 $p, 2p, \ldots, p^{k-1}p$),所以与 $p^k$ 互质的数有 $p^k - p^{k-1}$ 个。 -
欧拉函数是积性函数:若 $m, n$ 互质,则 $\varphi(mn) = \varphi(m) \varphi(n)$。
这个性质是欧拉函数的核心性质,也是推导其计算公式的基础。
欧拉函数的计算公式推导
对于任意正整数 $n$,我们可以将其质因数分解为 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$,其中 $p_1, p_2, \ldots, p_k$ 是不同的质数,$e_1, e_2, \ldots, e_k$ 是正整数。
利用欧拉函数的积性性质,我们有:
$$ \varphi(n) = \varphi(p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}) = \varphi(p_1^{e_1}) \varphi(p_2^{e_2}) \cdots \varphi(p_k^{e_k}) $$
再根据 $\varphi(p^k) = p^k - p^{k-1}$,我们得到:
$$ \varphi(n) = (p_1^{e_1} - p_1^{e_1-1})(p_2^{e_2} - p_2^{e_2-1}) \cdots (p_k^{e_k} - p_k^{e_k-1}) $$
进一步化简,得到:
$$ \varphi(n) = n \left( \frac{p_1 - 1}{p_1} \right) \left( \frac{p_2 - 1}{p_2} \right) \cdots \left(\frac{p_k - 1}{p_k} \right) $$
这就是欧拉函数的计算公式。
示例
例如,对于 $n = 12$,其质因数分解为 $12 = 2^2 \cdot 3^1$。
应用欧拉函数的计算公式,我们有:
$$ \varphi(12) = 12 \left( \frac{2-1}{2} \right) \left( \frac{3-1}{3} \right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4 $$
小于或等于 $12$ 的正整数中与 $12$ 互质的数有 $1, 5, 7, 11$,共 $4$ 个。
根据欧拉函数公式:
$$ \varphi(n) = n \left( \frac{p_1 - 1}{p_1} \right) \left( \frac{p_2 - 1}{p_2} \right) \cdots \left(\frac{p_k - 1}{p_k} \right) $$
要求一个数的欧拉函数,只需要求出这个数的所有质因子即可算出。
代码:
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
// 公式最前面的n
int res = n;
//求质因子
for(int i = 2; i <= n / i; i++)
{
if(n % i == 0)//找到质因子
{
// (p - 1) / p
// 先除后乘
res = res / i * (i - 1) ;
// 对 n 进行约分
while(n % i == 0) n = n / i;
}
}
// 如果有剩余,则剩余是个质因子
if( n > 1) res = res /n * (n - 1) ;
cout << res << endl;
}
return 0;
}
海绵宝宝的算法真的写的太棒了!