欧拉函数 \(\phi\)
定义
\(\phi(n)\) 表示 \(1 \sim n\) 中与 \(n\) 互质的数的个数。
公式
先将 \(n\) 分解质因数,即:
\(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\ \dots p_k^{\alpha_k}\)
则 \(\phi(n) = n \cdot \prod_{i=1}^k (1-\dfrac{1}{p_i})\)。
即 \(\phi(n) = n \cdot \left(1-\dfrac{1}{p_1}\right)\cdot \left(1-\dfrac{1}{p_2}\right)\dots\left(1-\dfrac{1}{p_k}\right)\)
也可以写成 \(\phi(n) = n \cdot \dfrac{p_1-1}{p_1}\cdot \dfrac{p_2-1}{p_2}\dots\dfrac{p_k-1}{p_k}\)
例如:
\(n = 6 = 2^1 \cdot 3^1\)
\(\phi(6) = 6 \cdot \left(1-\dfrac12 \right) \cdot \left(1-\dfrac13 \right) = 2\)
\(\phi(6) = 6 \cdot \dfrac{2-1}2 \cdot \dfrac{3-1}3 = 2\)
依据
推导
- 从 \(1 \sim n\) 中去掉 \(p_1,p_2,\dots,p_k\) 的所有倍数,即 \(n \gets n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)。
- 加上所有 \(p_i \cdot p_j\) 的倍数,即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)。
- 减去所有 \(p_i \cdot p_j \cdot p_k\) 的倍数,即 \(n \gets n-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。
- 加上所有 \(p_i \cdot p_j \cdot p_k \cdot p_l\) 的倍数,即 \(p_i \cdot p_j \cdot p_k\) 的倍数,即 \(n \gets n+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)。
因此,
$\phi(n) = $
\(n-\left \lfloor \dfrac{n}{p_1} \right \rfloor - \left \lfloor \dfrac{n}{p_2} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_k} \right \rfloor\)
\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_3} \right \rfloor + \dots + \left \lfloor \dfrac{n}{p_{k-1} \cdot p_k} \right \rfloor\)
\(-\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3} \right \rfloor - \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_4} \right \rfloor - \dots - \left \lfloor \dfrac{n}{p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)
\(+\left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_4} \right \rfloor + \left \lfloor \dfrac{n}{p_1 \cdot p_2 \cdot p_3 \cdot p_5} \right \rfloor + \dots +- \left \lfloor \dfrac{n}{p_{k-3} \cdot p_{k-2} \cdot p_{k-1} \cdot p_k} \right \rfloor\)
\(- \dots\)
也就是 \(n\) 减去奇数个质因子的倍数,加上偶数个质因子的倍数,循环往复。
将上式等价变形,得到刚才提到的公式。
代码
cin >> n;
res = n; // 初始值为 n
for(int i=2; i<=n/i; i++){
// 如果 i 是 n 的质因子
if(n%i == 0){
res = res / i * (i - 1);
// 或 res * (1 - 1 / i);
// 或 res * ((i - 1) / i);
// 但如果使用后面 2 种,则需要考虑实数问题
while(n%i == 0){
n /= i;
}
}
}
// 如果还剩下大于根号 n 的质因子,再次统计到答案种
if(n > 1){
res = res / n * (n - 1);
}
cout << res;
求多个数欧拉函数之和
求 \(1\) 个数的欧拉函数时间复杂度是 \(\Theta(\sqrt{n})\),求 \(n\) 个数的时间复杂度即 \(\Theta(n \cdot \sqrt{n})\),那如何进行优化,使其变成 \(\Theta(n)\) 呢?
可以先线性地筛出 \(n\) 以内的所有质数,在进行求解。
线性筛指数的代码如下:
for(int i=2; i<=n; i++){
if(!st[i]){
p[cnt++] = i;
}
for(int j=0; p[j] <= n/i; j++){
st[p[j] * i] = 1;
if(i%p[j] == 0){
break;
}
}
}
如何对其进行修改呢?
边界条件
从定义出发设置边界条件,即 \(\phi(1) = 1\)。
如果 \(i\) 是质数
如果 \(i\) 是质数,那么在 \(1 \sim n\) 当中 \(1 \sim n-1\) 都是与其互质的数,即 \(\phi(i) = i-1\)。
内层循环
如果 \(p_j\) 是 \(i\) 的最小质因子
因为一个数分解质因数后的指数与欧拉函数结果无关,因此 \(p_j \cdot i\) 和 \(i\) 的质因子是相同的,因为将 \(p_j \cdot i\) 和 \(i\) 分解质因数后,\(p_j \cdot i\) 只会比 \(i\) 的指数多1。
我们假设 \(i\) 的质因子是 \(q_1,q_2,\dots,q_k\),那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。
由于 \(p_j\) 是 \(i\) 的质因子,又因为 \(p_j \cdot i\) 的质因子与 \(i\) 相同,那么,
\(\phi(p_j\cdot i) = p_j \cdot i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。
其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同,所以我们可以下结论:
\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \]如果 \(p_j\) 不是 \(i\) 的最小质因子
那么 \(p_j\) 就是 \(p_j \cdot i\) 的最小质因子,且 \(p_j\) 是不包含在 \(i\) 的质因子当中的。
因此,假设 \(i\) 的所有质因子是 \(q_1, q_2,\dots,q_k\),那么 \(\phi(i) = i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\)。
则 \(\phi(p_j \cdot i) = p_j \cdot i \cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right) \cdot \left(1-\dfrac{1}{p_j}\right)\)。
其中的 \(i\cdot \left(1-\dfrac{1}{q_1}\right)\cdot \left(1-\dfrac{1}{q_2}\right)\dots\left(1-\dfrac{1}{q_k}\right)\) 与 \(\phi(i)\) 相同,所以我们可以下结论:
\[\phi(p_j \cdot i) = p_j \cdot \phi(i) \cdot \left( 1-\dfrac{1}{p_j}\right) = \phi(i) \cdot (p_j - 1) \]代码
int get_phi(int n){
phi[1] = 1; // 特殊规定
for(int i=2; i<=n; i++){
if(!st[i]){
p[cnt++] = i;
phi[i] = i - 1; // 如果 i 是质数,它的欧拉函数是 i-1
}
for(int j=0; p[j] <= n/i; j++){
st[p[j]*i] = 1; // p[j] * i 不是质数
if(i % p[j] == 0){ // p[j] 是 i 的最小质因子
phi[p[j] * i] = phi[i] * p[j];
break;
}
else{ // p[j] 是 p[j] * i 的最小质因子
phi[p[j] * i] = phi[i] * (p[j] - 1);
}
}
}
int res = 0;
// 统计所有数的欧拉函数之和
for(int i=1; i<=n; i++){
res += phi[i];
}
// 返回
return res;
}
欧拉定理
若 \(a\) 与 \(n\) 互质,则有 \(a^{\phi(n)} \equiv 1 (\bmod\ n)\)。
标签:lfloor,right,函数,cdot,dfrac,rfloor,欧拉,left From: https://www.cnblogs.com/2huk/p/17297307.html