欧拉函数

定义

欧拉函数（Euler’s totient function），即，表示的是小于等于和互质的数的个数。

比如说。

当是质数的时候，显然有。

性质

积性函数

即对任意满足的整数，有。

特别地，当是奇数时。

证明参见剩余系的复合。

等式

证明

方法一：组合计数法 (最直观)

这种方法的思想是：我们考虑一个大小为 n 的集合，然后用两种不同的方法来对它进行计数。

第一步：定义我们的集合

考虑集合。这个集合的大小显然是 n。

第二步：对集合进行划分

我们将集合 S 中的 n 个数，根据它们与 n 的最大公约数（GCD）进行分类。

对于 n 的每一个正因子 d，我们定义一个子集：

也就是说，包含了 1到n 中所有与 n 的最大公约数为 d 的数。

例如，当 n = 12 时：
n 的因子 d 有: 1, 2, 3, 4, 6, 12。

第三步：证明这是一个划分

不重不漏：对于集合 S 中的任何一个数 k（），gcd(k, n) 的值必然是 n 的一个因子 d。因此，k 必然属于且仅属于某一个子集。
不相交：如果，那么和不可能有相同的元素，因为一个数与 n 的最大公约数是唯一的。

因此，这些子集构成了集合 S 的一个划分（Partition）。这意味着 S 的总元素个数等于所有子集元素个数之和。

因为，所以：

第四步：计算每个子集的大小

现在我们的任务就是计算是多少。
根据定义，是满足以下两个条件的整数 k 的个数：

从条件出发，我们可以得到：

d 必须是 k 的因子，所以 k 可以写成的形式，其中 m 是某个整数。
将和代入 gcd(k, n) = d，我们得到。
利用 GCD 的性质，我们有。
两边除以 d，得到。

现在我们来看 m 的取值范围。由，可得，两边同时除以 d，得到。因为 m 是整数，所以。

综上所述，寻找满足条件的 k 的个数，就等价于寻找满足以下条件的整数 m 的个数：

根据欧拉函数的定义（小于等于 x 且与 x 互质的正整数的个数），满足这两个条件的 m 的个数正好是。
所以，我们得到了一个关键结论：

第五步：完成证明

将代入第三步的求和式：

现在我们观察这个求和。当 d 遍历 n 的所有因子时，n/d 同样也遍历了 n 的所有因子。
例如，当 n=12 时：

d 的取值是 {1, 2, 3, 4, 6, 12}
n/d 的取值是 {12, 6, 4, 3, 2, 1}
它们是同一组数，只是顺序不同。

因此，对求和与对求和的结果是完全一样的：

（这里我们让）

所以，我们最终证明了：

方法二：利用乘性函数（更抽象）

这个证明需要一些预备知识：

算术函数：定义域为正整数的函数。
乘性函数：如果算术函数 f 满足，对于任意互质的正整数 m 和 n，都有，则称 f 为乘性函数。就是一个乘性函数。
狄利克雷卷积 (Dirichlet Convolution)：两个算术函数 f 和 g 的狄利克雷卷积定义为。
一个重要定理：如果 f 和 g 是乘性函数，那么它们的狄利克雷卷积 f*g 也是乘性函数。

证明过程：

定义两个函数：和 (对于所有n，函数值都为1)。这两个都是乘性函数。
我们想证明的恒等式是。
这个和式可以写成狄利克雷卷积的形式：。
所以我们要证明的其实是。
我们定义函数。因为和 u 都是乘性函数，所以 g 也是乘性函数。
对于乘性函数，我们只需要验证它在素数幂 （p是素数，k≥1）上成立，就可以推广到所有正整数。
让我们来计算：

的因子只有。

我们知道，并且对于素数幂 (当 )。

这是一个伸缩和（Telescoping Sum）：
所以我们证明了。也就是说，对于任何素数幂，都有。
因为 g 是乘性函数，而 (恒等函数) 也是乘性函数。两个乘性函数在所有素数幂上的取值都相等，那么它们在所有正整数上的取值都相等。
因此，对于所有正整数 n，都有，即。

这两种方法都非常漂亮，第一种更直观，第二种则展示了数论中乘性函数和狄利克雷卷积的威力。

若为质数，。其中被排除的数为。
由唯一分解定理，设，其中是质数，又由积性，有。

筛法求欧拉函数

注意到在线性筛中，每一个合数都是被最小的质因子筛掉。比如设是的最小质因子，，那么线性筛的过程中通过筛掉。

观察线性筛的过程，我们还需要处理两个部分，下面对分情况讨论。

如果，那么包含了的所有质因子。

那如果呢，这时和是互质的，根据欧拉函数性质，我们有：

int phi[MAXN];
vector<int> primes;
bitset<MAXN> nonprime;

inline void Euler(int lim) {
    nonprime[1] = true;
    phi[1] = 1;
    for (int p = 2; p <= lim; ++p) {
        if (!nonprime[p]) {
            primes.push_back(p);
            phi[p] = p - 1;
        }
        for (int pri: primes) {
            if (pri * p > lim)
                break;
            nonprime[pri * p] = true;
            if (p % pri == 0) {
                phi[pri * p] = pri * phi[p];
                break;
            }
            phi[pri * p] = phi[pri] * phi[p];
        }
    }
}

应用

欧拉函数常常用于化简一列最大公约数的和。国内有些文章称它为 欧拉反演。

在结论中代入，则有

其中，称为 Iverson 括号，只有当命题为真时取值为，否则取。对上式求和，就可以得到

这里关键的观察是，即在和之间能够被整除的的个数是。

利用这个式子，就可以遍历约数求和了。需要多组查询的时候，可以预处理欧拉函数的前缀和，利用数论分块查询。

GCD SUM

给定，求

思路

仿照上文的推导，可以得出

此时需要从遍历到求欧拉函数，用线性筛做就可以得到答案。

核心思想

推导的核心是利用下面这个关键恒等式：

这个恒等式表明，任何正整数 k 都等于它所有因子的欧拉函数值之和。其中 d|k 表示 d 是 k 的一个因子，φ(d) 是欧拉函数，表示小于等于 d 且与 d 互质的正整数的个数。

推导步骤

我们的目标是推导：

第一步：应用核心恒等式

我们将上述核心恒等式应用到 gcd(i, j) 上。令 k = gcd(i, j)，则有：

现在，我们将这个表达式代入到我们要求的和式中：

第二步：改变求和顺序

这是一个三重求和。直接计算非常困难。我们的策略是改变求和的顺序。原来是先遍历 i 和 j，再遍历 d。我们现在希望先遍历 d。

首先，我们来分析求和的条件 d | gcd(i, j)。这个条件等价于两个子条件：

d | i (d 整除 i)
d | j (d 整除 j)

同时，由于 i 和 j 的范围是 1 到 n，d 作为它们的因子，d 的取值范围也必然在 1 到 n 之间。

因此，我们可以把求和顺序改为：先枚举所有可能的 d（从 1 到 n），然后对于每一个 d，我们再去计算有多少对 (i, j) 满足 d | i 和 d | j 的条件。

第三步：简化内部求和

在上面的表达式中，φ(d) 的值只与 d 有关，与 i 和 j 无关。因此，我们可以将 φ(d) 提到内部两个求和符号的前面：

现在，我们来计算括号里的部分：

这个表达式实际上是两个独立的求和的乘积：

我们来分析其中一个求和：\sum_{i=1, d|i}^n 1
这个求和的含义是：在 1 到 n 的范围内，有多少个整数 i 是 d 的倍数。
这些数是 d, 2d, 3d, ..., kd，其中 kd ≤ n。
满足这个条件的最大整数 k 就是 ⌊n/d⌋ (向下取整)。
所以，1 到 n 中 d 的倍数一共有 ⌊n/d⌋ 个。

因此：

同理：

将这两个结果相乘，我们得到括号里的值为：

第四步：得到最终结果

将上一步得到的结果代回到 S 的表达式中：

这样，我们就成功地将左边的式子推导成了右边的式子。