数学 - 欧拉函数与欧拉定理

模板

欧拉函数

欧拉函数 $\varphi(N)$ 的定义如下：在 1 ~ N 中所有与 N 互质的数字的个数，计算如下：

$$\begin{aligned} N&=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}\\ \varphi(N)&=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots(1-\frac{1}{p_n}) \end{aligned}$$

证明需要用到容斥原理：先把所有 $p_i$ 的倍数排除，这时会把 $p_ip_j$ 的倍数排除两遍，把 $p_ip_jp_k$ 的倍数排除三遍；于是加入 $p_ip_j$ 的倍数，这样会把 $p_ip_jp_k$ 的倍数加入三遍；然后再排除 $p_ip_jp_k$ 的倍数… 如下：

$$\begin{aligned} \varphi(N)=N&-\frac{N}{p_1}-\frac{N}{p_2}-\frac{N}{p_3}\cdots\\ &+\frac{N}{p_1p_2}+\frac{N}{p_2p_3}+\frac{N}{p_1p_3}+\cdots\\ &-\frac{N}{p_1p_2p_3}-\cdots\\ \end{aligned}$$

观察到，所有奇数个 p 相乘的都为负，所有偶数个相乘的都为正，而且相乘的个数取决于有多少个p，因此开头给出的定义式展开符合这一点。

可以进一步说明，对于有 m 个 p 相乘的项共有 $C_n^m$ 个，开头给出的式子中，在 n 个括号中选出 m 个含 p 的项相乘共有 $C_n^m$ 中选法，所以等式成立。

欧拉定理

若 $a$ 与 $x$ 互质，则 $a^{\varphi(x)}\equiv 1 (\text{mod }x)$，证明如下（下面所有的 $k_i, K_i$ 都代表某个整数）：

设所有小于 $x$ 的数中所有与 $x$ 互质的数是 $x_1, x_2, \cdots, x_{\varphi(x)}$，那么 $ax_1, ax_2, \cdots, ax_{\varphi(x)}$ 也与 $x$ 互质（无论是 $a$ 还是 $x_i$ 都与 $x$ 没有相同的质因数，所以 $ax_i$ 也与 $x$ 没有相同的质因数）。

并且 $ax_1, ax_2, \cdots, ax_{\varphi(x)}$ 对 $x$ 取模两两不相同，这步用反证法证明，假设 $ax_i, ax_j$ 同余：

$$\begin{aligned} ax_i-ax_j&=(k_1-k_2)x\\ &=a(x_i-x_j)\\ \end{aligned}$$

由于 $a$ 与 $x$ 互质，那么如果这个等式成立只能有 $x_i-x_j=K_1x$，又因为 $x_i-x_j<x$，所以矛盾。

于是这两组数模 $x$ 之后其实是同一组数据，那么它们取模之后全部乘起来结果是相同的。这里两边再取一遍模，使用模运算的乘法分配律。

$$\begin{aligned} \prod_{i=1}^{\phi(x)}[(ax_i)\text{ mod }x]&=\prod_{i=1}^{\phi(x)}x_i\\ a^{\phi(x)}\prod_{i=1}^{\phi(x)}x_i&\equiv \prod_{i=1}^{\phi(x)}x_i (\text{mod }x)\\ \end{aligned}$$

由于任意一个 $x_i$ 都与 $x$ 互质，所以它们的乘积也与 $x$ 互质，设它们的乘积为 $b \ne K_2x$，有：

$$\begin{aligned} a^{\varphi(x)}b&=k_1x+r,b=k_2x+r\\ a^{\varphi(x)}b-b&=(a^{\varphi(x)}-1)b\\ &=(k_1-k_2)x\\ &\Rightarrow a^{\varphi(x)}-1=K_3x\\ &\Rightarrow a^{\varphi(x)}\equiv 1 (\text{mod }x) \end{aligned}$$

特别地，如果设 $p$ 是质数，那么 $a^{\varphi(p)}\equiv a^{p-1} \equiv 1(\text{mod }p)$，欧拉定理是费马小定理的拓展。

定义法求欧拉函数

先找质因数，然后累项求积。

int euler(int a) {
    int res = a;
    for (int i = 2; i <= a/i; i++) {
        // 这里就是先用 if 然后在里面把 a 除干净
        if (a % i == 0) {
            // res(1-1/i) = res-res/i
            res = res - res/i;
            while (a % i == 0) a /= i;
        }
    }
    // 一定注意不要落了 a 没除干净的情况
    if (a > 1) res = res-res/a;
    return res;
}

线性筛选法求欧拉函数

与筛选质数时的模板类似。

#include <bitset>
#include <iostream>
using namespace std;

const int N = 1e6+10;
int phi[N], primes[N], cnt=0;
bitset<N> st;

void eular(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i-1;
        }
        for (int j = 0; primes[j] <= n/i; j++) {
            st[i * primes[j]] = 1;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            } else {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

可以证明当要求 $i\cdot p_j$ 的时候，$\varphi(i)$ 一定已经求出来了：

1. 如果 $i$ 是质数，那么它会在进入内层 for 循环前被求出来。
2. 如果 $i$ 是合数，那么它会在 $i$ 循环到自己之前就被筛掉，筛掉的同时也就求出来了 $\varphi(i)$。

接下来通过公式证明 $\varphi(i)$ 的这几个递推式：

1. 如果 $i$ 是质数，那么在 $1 \sim i-1$ 中所有数都与它互质，所以有 $\varphi(i)=i-1$。
2. 如果 $i \text{ mod } p_j=0$，此时 $p_j$ 是 $i$ 的最小质因数，$i$ 表示为 $p_1^{\alpha_1}p_2^{\alpha_2}\cdots$ 这个式子中一定包含了 $p_j$，由欧拉函数的定义知，$\varphi(p_j\cdot i)=p_j\varphi(i)$。
3. 如果 $i\text{ mod }p_j\ne 0$，此时 $p_j$ 不是 $i$ 的质因数，那么 $\varphi(p_j\cdot i)=\varphi(p_j)\cdot \varphi(i)=(p_j-1)\varphi(i)$。

例题

可见的点

在一个平面直角坐标系的第一象限内，如果一个点 (x,y) 与原点 (0,0) 的连线中没有通过其他任何点，则称该点在原点处是可见的。

例如，点 (4,2) 就是不可见的，因为它与原点的连线会通过点 (2,1)。

编写一个程序，计算给定整数 N 的情况下，满足 0≤x, y≤N 的可见点 (x，y) 的数量（可见点不包括原点）。

题目链接：AcWing 201。

如果一个点 $(x_0,y_0)$ 可见，必有 $k=y_0/x_0$ 不可化简，也就是 $y_0, x_0$ 互质。

所以答案是 $2\sum_{i=1}^n \varphi(i)+1$，去掉一个直线 $y=x$，加上两个直线 $y=0,x=0$

#include <iostream>
#include <vector>
using namespace std;

const int N = 1010, m = N-1;
int phi[N];
bool st[N];
vector<int> primes;

void init() {
    phi[1] = 1;
    for (int i = 2; i <= m; i++) {
        if (!st[i]) {
            primes.push_back(i);
            phi[i] = i-1;
        }
        for (int j = 0; primes[j] <= m/i; j++) {
            st[i*primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[i*primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i*primes[j]] = phi[i] * (primes[j]-1);
        }
    }
}

int main() {
    init();
    int T; scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        int n, sum = 0;
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
            sum += phi[j];
        printf("%d %d %d\n", i, n, 2*sum+1);
    }
    return 0;
}

最大公约数

给定整数 N，求 1≤x,y≤N 且 GCD(x,y) 为素数的数对 (x,y) 有多少对。

题目链接：AcWing 220。

题目是求（中间当作一个布尔表达式）：

$$\sum_p \sum _{i=1}^n\sum_{j=1}^n [\gcd(i,j)=p]$$

若 $i,j$ 为 $p$ 的倍数，那么下列式子等价：

$$\gcd(i,j)=p \Leftrightarrow \gcd(i/p,j/p)=1$$

因此枚举 $i,j=kp$ 中的 $k$ 就可以：

$$\sum_p \sum_{i=1}^{\lfloor n/p \rfloor}\sum_{j=1}^{\lfloor n/p \rfloor}[\gcd(i,j)=1]$$

等价于：

$$\sum_p[2\sum_{i=1}^{\lfloor n/p \rfloor} \varphi(i)-1]$$

对欧拉函数简单求一个前缀和就可以。

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
const int N = 1e7+10;
int phi[N];
LL s[N];
bool st[N];
vector<int> primes;

void init(int n) {
    s[1] = phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes.push_back(i);
            phi[i] = i-1;
        }
        
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j]*i] = true;
            if (i % primes[j] == 0) {
                phi[primes[j]*i] = phi[i]*primes[j];
                break;
            }
            phi[primes[j]*i] = phi[i]*(primes[j]-1);
        }
        
        s[i] = s[i-1] + phi[i];
    }
}

int main() {
    int n;
    cin >> n;
    init(n);
    LL ans = 0;
    for (int p : primes) {
        ans += 2*s[n/p]-1;
    }
    cout << ans << endl;
    return 0;
}

最大公约数求和

给定一个整数 $N$，求出 $\sum_{i=1}^n\gcd(i,n)$

题目链接：P2303，AcWing 221。

首先一定有 $\gcd(i,n)|n$，因此枚举 $n$ 的所有约数，看它在整个过程中出现了几次。

对于其中一个约数 $d$，当 $\gcd(i,n)=d$ 时，有 $\gcd(i/d,n/d)=1$，其中 $i/d\in[1,n/d]$，因此它出现的个数就是 $\varphi(n/d)$，这样就有：

$$\begin{aligned} \sum_{i=1}^n\gcd(i,n)&=\sum_{d|n}d\varphi(\frac{n}{d})\\ &=\sum_{d|n}\frac{n}{d}\varphi(d)\\ &=n\sum_{d|n}\prod_{i=1}^{k_d}(1-\frac{1}{p_i}) \end{aligned}$$

这里有一个常用的技巧，就是如果是枚举所有约数的某个性质的和，可以借鉴约数之和公式。

$$(1+p_1^1+p_1^2+\cdots+p_1^{c_1})(1+p_2^1+p_2^2+\cdots+p_2^{c_2})\cdots$$

映射到下面：

$$[1+(1-\frac{1}{p_1})+(1-\frac{1}{p_1})+\cdots+(1-\frac{1}{p_1})]\cdots\\ =\prod_{i=1}^k [1+c_i(1-\frac{1}{p_i})]$$

所以原式等于：

$$n\prod_{i=1}^k[1+c_i(1-\frac{1}{p_i})]$$

#include <cstdio>
using namespace std;

typedef long long LL;

int main() {
    LL n;
    scanf("%lld", &n);
    LL res = n;
    
    for (int i = 2; i <= n/i; i++) {
        if (n % i == 0) {
            int c = 0, p = i;
            while (n % i == 0) n /= i, c++;
            // 先除再乘防溢出
            res /= p;
            res = res * (p + c*(p-1));
        }
    }
    if (n > 1) {
        res /= n;
        res = res * (n + n - 1);
    }
    printf("%lld\n", res);
    return 0;
}