笔记汇总
欧拉函数的定义
$1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。
若在算数基本定理中，$N=p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m$，则：
$\varphi(N) = N × \frac{p_1−1}{p_1} × \frac{p_2−1}{p_2} × … × \frac{p_m−1}{p_m}$
证明 $(proof)$
定义 $(definition)$
互质：公约数只有 $1$ 的两个整数互质
边界 $(basis)$
$\varphi(1) = 1$，小于等于 $1$ 的正整数只有 $1$，
稍微扩展一下 ∼hh
$\varphi(1) = 1$， $\varphi(2) = 1$， $\varphi(3) = 2$
$\varphi(4) = 2$， $\varphi(5) = 4$， $\varphi(6) = 2$
$\varphi(7) = 6$， $\varphi(8) = 4$， $\varphi(9) = 6$
$\varphi(10) = 5$，$\varphi(11) = 10$，$\varphi(12) = 4$
规律 1
可以发现，对于两个互质的数 $m,n$，满足 $\varphi(mn) = \varphi(m) * \varphi(n)$，例如
$\varphi(6) = \varphi(2) * \varphi(3) = 1 * 2 = 2$
$\varphi(12) = \varphi(3) * \varphi(4) = 2 * 2 = 4$
这个性质很好证明：
如果一个数 $d$ 与 $n$ 互质，则 $d$ 肯定也与 $n * m$ 互质。
若有一个数 $c$ 与 $n * m$ 互质，则可以推论出 $d * c$ 同样与 $n * m$ 互质。
根据乘法原理可证。
规律 2
$\varphi(a^b) = a^b - a^{b-1}$，例如
$\varphi(4) = 2^2 - 2^{2-1} = 2$
$\varphi(9) = 3^2 - 3^{2-1} = 6$
让我们来写一个优美的证明：
因为 $\varphi(a^b)$ 表示 从 $1$ 到 $a^b$ 中与 $a^b$ 互质的数。
我们用排除法解决，在 $\varphi(a^b)$ 中，不与 $a^b$ 互质的数有 $a、2a…a^{b-1}*a$ 共 $a^{b-1}$ 个数。
所以 $\varphi(a^b) = a^b - a^{b-1}$，得证。
规律扩展
因为 $N=p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m$
所以 $\varphi(N)=\varphi(p^{a_1}_1) * \varphi(p^{a_2}_2) * … * \varphi(p^{a_m}_m)$
代入 $\varphi(a^b) = a^b - a^{b-1}$ 得
$\varphi(N) = (p^{a_1}_1 - p^{a_1 - 1}_1) * (p^{a_2}_2 - p^{a_2 - 1}_2) * … * (p^{a_m}_m - p^{a_m - 1}_m)$
又因为 $a^b - a^{b-1} = a^b * (1 - \frac{1}{a})$
所以 $\varphi(N) = p^{a_1}_1 * p^{a_2}_2 * … * p^{a_m}_m * (1 - \frac{1}{p_1}) * (1 - \frac{1}{p_2}) * … * (1 - \frac{1}{p_m}) = N * \displaystyle\prod_{i = 1}^{m}(1 - \frac{1}{p_i})$
得证。
性质 1
质数 的欧拉函数 等于 原值 $- 1$，例如
$\varphi(2) = 1$， $\varphi(3) = 2$
$\varphi(5) = 4$， $\varphi(7) = 6$
因为 质数 与除其本身外的所有 小于它 的数互质
性质 2
设 $d$ 为一个质数，其倍数为 $kd$
有 $\varphi(d * kd) = \varphi(kd) * d$
这是因为 $\varphi(d * kd)$ 中，不与 $d * kd$ 互质的数有 $d、2d…d * (kd)$ 共 $kd$ 个数。
所以 $\varphi(d * kd) = d * kd - (kd) = (d - 1) * kd = (kd - k) * d = \varphi(kd) * d$
代码
试除法求欧拉函数
将 $n$ 分解质因数，对于其质因数 $p_i$，$res = res * \frac{1}{p_i}$
其余同 分解质因数 。
时间复杂度： $O(\sqrt{n})$
LL phi(int n)
{
LL res = n;
for (int i = 2; i <= n / i; i ++ )
if (n % i == 0)
{
res = res / i * (i - 1);
while (n % i == 0) n /= i; // 消除所有此质因子，一个质因子只记录一次
}
if (n > 1) res = res / n * (n - 1); // 消除小于 sqrt(n) 的质因子后还有质因子，就是大于 sqrt(n) 的
// 一个数最多只有一个大于 sqrt(n) 的质因子
return res;
}
筛法求欧拉函数
因为欧拉函数的关键是 分解质因数，所以可以直接套一个 线性筛。
对于一个 质数，其 欧拉函数 等于原值 $- 1$。（性质 1）
又因为 质数 与除其 倍数 以外的任意自然数都 互质，
所以可以在 标记合数时 顺带计算合数的 欧拉函数（规律 1）
若 合数 与 质数 呈倍数关系时，有 $\varphi(d * kd) = \varphi(kd) * d$ （性质 2）
时间复杂度： $O(n)$
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
区间内判断最大公约数为素数的方案数
本题要求的是 $x, y <= n$ 时 $gcd(x, y)$ 为质数的方案数。
因为 $gcd$ 的结果不唯一，所以我们要进行化简。
设 $p$ 为一个质数，则满足 $gcd(x, y) = p$ 时，有 $gcd( \frac{x}{p} , \frac{y}{p} ) = 1$
由此将问题转化为解决 $gcd(x, y) = 1$ 的方案数，也就是 $x$ 和 $y$ 互质的方案数。
将 $x$ 与 $y$ 之间的关系分成两类 $x > y$ 和 $x < y$。
对于其中任意一类，都可以转化为求出 $1$ 到 $n$ 中每个数的欧拉函数，
也就是当确定 $x$ 的值时，计算 $y$ 有多少种不同情况，令 $x$ 和 $y$ 互质。
值得注意的是，$x = y$ 时，也为互质，这要进行特判。
用数组 $s$，统计前缀和 $s[i] = s[i - 1] + * phi[i]$
记得将预处理的数组转化为实际答案。
枚举质数 $p_i$，将答案累计，注意其上界为 $n / p_i$ 下取整。
$res += 2 * s[n / p_i] + 1$
时间复杂度： $O(n)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int n, m;
long long phi[N], p[N], v[N], s[N];
long long res;
inline bool check(int a, int b) // a % b 的常数优化
{
return a / b * b == a;
}
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!v[i])
{
p[ ++ m] = i;
phi[i] = i - 1;
}
for (int j = 1; p[j] <= n / i; j ++ )
{
v[i * p[j]] = 1;
if (check(i, p[j]))
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + phi[i]; // 前缀和
for (int i = 1; i <= m; i ++ ) res = res + s[n / p[i]] * 2 + 1; // 两种情况加特殊
}
int main()
{
scanf("%d", &n);
init(n);
printf("%lld", res);
}
