欧拉函数
欧拉函数定义
\(1 \sim n\) 中与 \(n\) 互质的数的个数称为欧拉函数，记为 \(\phi(n)\)
在算数基本定理中，\(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n}\)
则 \(\phi(n) = n \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_n - 1}{p_n}\)
欧拉函数证明
在 \(1 \sim n\) 内：
-
若 \(n = 1\)，则 \(\phi(1) = 1\) ，1 与 1 互质。
-
若 \(n\) 是质数，则 \(\phi(n) = n - 1\)，与质数 \(n\) 互质的数是 \(1 \sim n - 1\)。
-
若 \(n\) 是质数的某几次方：\(n = p^k\)，则在 \(1 \sim n\) 内与 \(n\) 不互质的有：
\(p、2p、3p、\cdots、p^{k - 1}p\)
总共有 \(p^{k - 1}\) 个与 \(n\) 不互质的，所以 \(\phi(n) = p^k - p^{k - 1} = p^k \times (1 - \frac{1}{p})\)
-
若 \(n\) 是两个互质的数的乘积：\(n = a \times b\)，则 \(\phi(n) = \phi(a) \times \phi(b)\)，证明请看下一章。
有了上面的基础之后，根据算术基本定理有：
\(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n}\)
并且 \(p_1^{a_1}、p_2^{a_2}、\cdots 、p_n^{a_n}\) 任意一对都互质，所以根据上面的推理第 4 点有：
\(\phi(n) = \phi(p_1^{a_1}) \times \phi(p_2^{a_2}) \times \cdots \phi(p_n^{a_n})\)
再根据上面的推理第 3 点我们对每一项 \(\phi(p_k^{a_k})\) 都能分解成：
\(\phi(p_k^{a_k}) = p_k^{a_k} - p_k^{a_k - 1}\)
所以 \(\phi(n) = (p_1^{a_1} - p_1^{a_1 - 1}) \times (p_2^{a_2} - p_2^{a_2 - 1}) \times \cdots \times (p_n^{a_n} - p_n^{a_n - 1})\)
进一步化简得：\(\phi(n) = p_1^{a_1} \times (1 - \frac{1}{p_1}) \times p_2^{a_2} \times (1 - \frac{1}{p_2}) \times \cdots \times p_n^{a_n} \times (1 - \frac{1}{p_n})\)
而由前面的算术基本定理：\(n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n}\)
所以：
\[\begin{aligned} \phi(n) &= p_1^{a_1} \times (1 - \frac{1}{p_1}) \times p_2^{a_2} \times (1 - \frac{1}{p_2}) \times \cdots \times p_n^{a_n} \times (1 - \frac{1}{p_n}) \\ &= p_1^{a_1} \times p_2^{a_3} \times \cdots \times p_n^{a_n} \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n}) \\ &= n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n}) \end{aligned}\]
给定 \(n\) 个正整数 \(a_i\)，叫你求这每一个数的欧拉函数。
代码参考
// 如何将自己的心中所想，用 「文字」、「语言」、「图像」 记录下来
typedef long long ll;
const int N = int (1e7 + 10);
int n;
int a[N], b[N];
void get_ds(int n)
{
b[0] = 0;
for (int i = 2; i <= n / i; i ++)
{
if (n % i == 0)
{
while (n % i == 0) n /= i;
b[++b[0]] = i;
}
}
if (n > 1) b[++b[0]] = n;
}
void solve(void)
{
scanf ("%d", &n); for (int i = 1; i <= n; i ++) scanf ("%d", a + i);
for (int i = 1; i <= n; i ++)
{
ll ans = a[i]; get_ds(a[i]);
for (int i = 1; i <= b[0]; i ++) ans = ans / b[i] * (b[i] - 1);
printf ("%lld\n", ans);
}
}
// 并能使读者与我达成共鸣，是我为什么而学习的最本质的追求
给定一个整数 \(n\)，叫你求 \(1 \sim n\) 中所有数的欧拉函数之和。
思路:
假设给定了数据：\([1, 2, 3, 4, 5, 6, 7 ,8]\)
我们可以很轻松地求出质数 \(2、3、5、7\) 的欧拉函数：\(\phi(prime) = prime - 1\)，当然 \(\phi(1) = 1\)，这是显而易见的
再根据上面的推理第 4 点：
若 \(n\) 是两个互质的数的乘积：\(n = a \times b\)，则 \(\phi(n) = \phi(a) \times \phi(b)\)
则若知道两个数 \(i、j\) 的 \(\phi(i)\) 和 \(\phi(j)\) ，其中 \(i\) 是质数，且 \(j \bmod i \neq 0\)，说明 \(i、j\) 互质，所以 \(\phi(i \times j) = \phi(i) \times \phi(j)\)
但若 \(j \bmod i = 0\)，说明 \(i\) 是 \(j\) 的质因子，由上面的欧拉公式：
\(\phi(n) = n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n})\)
则 :
\(\phi(j) = j \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n})\)
\(\phi(j \times i) = j \times i \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_n}) = \phi(j) \times i\)
因此我们可以借助欧拉筛质数法来求出 \(1 \sim n\) 内所有数的欧拉函数之和。
代码参考
#include <bits/stdc++.h>
using namespace std;
int debuggersum = 0;
typedef long long ll;
typedef long double ld;
typedef __int128_t int128;
// 如何将自己的心中所想，用 「文字」、「语言」、「图像」 记录下来
const int N = int (1e7 + 10);
ll p[N], d[N], e[N], cnt;
int n;
void get_p(int n)
{
e[1] = 1;
for (int i = 2; i <= n; i ++)
{
if (d[i] == 0) p[cnt ++] = i, e[i] = i - 1;
for (int j = 0; p[j] <= n / i; j ++)
{
d[p[j] * i] = 1;
if (i % p[j] == 0)
{
e[p[j] * i] = p[j] * e[i]; break;
}
else e[p[j] * i] = e[p[j]] * e[i];
}
}
}
void solve(void)
{
scanf ("%d", &n);
get_p(n);
ll ans = 0;
for (int i = 1; i <= n; i ++) ans += e[i];
printf ("%lld\n", ans);
}
// 并能使读者与我达成共鸣，是我为什么而学习的最本质的追求
int main(void)
{
solve();
}