漫谈剩余系理论 & 欧拉定理 & 扩展欧拉定理

Link_Cut_Y · 2023-12-09 11:02:42 · 算法·理论

欧拉函数

欧拉函数定义为：\varphi(n) 表示 1 \sim n 中所有与 n 互质的数的个数。

关于欧拉函数有下面的性质和用途：

• 欧拉函数是积性函数。可以通过这个性质求出他的公式。

  • 假设 n = \prod^k p_i ^ {c_i}，则 f(n) = \prod^k f(p_i ^ {c_i}) = \prod^k p_k ^ {c_k - 1}(p_k - 1) = n \prod^k \dfrac{p_k - 1}{p_k}。

• 欧拉函数可以用线性筛筛出来。

  假设当前的数是 n，遍历到的质数为 p，那么 m = p \times n 肯定要被筛掉。根据欧拉筛：

  • 若 p | n，那么 p 是 n 的最小质因子，且 n 中包含 m 的所有质因子。根据单个欧拉函数的求法可以得到：\varphi(m) = \varphi(n) \times p。

  • 否则，p 和 n 互质，根据积性函数的性质，\varphi(m) = \varphi(n) \varphi(p)。

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;
        for (int j = 1; j <= cnt and 1ll * i * p[j] <= n; j ++ ) {
            st[i * p[j]] = true; if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j]; break;
            } phi[i * p[j]] = phi[i] * phi[p[j]];
        }
    }
}

• 欧拉函数可以用来降幂。下面就来介绍。

完全剩余系

对于整数集 S = \{r_1, r_2 \cdots r_n\} 满足：

• 任意不同元素 r_i, r_j，都有 r_i \not \equiv r_j(\bmod \ m)。

例如，对于 m = 5，S = \{0, 1, 2, 3, 4\} 就是 5 的一个完全剩余系。通常地，将模 m 的完全剩余系记做 \mathbb{Z_m}。

实际应用中，通常用 \mathbb{Z_m} = \{0, 1, 2 \cdots m - 1\} 来表示，也就是模 m 的最小非负完全剩余系。

推论 1：任意 m 个连续整数构成模 m 的完全剩余系。

推论 2：若 a \bot m 且 \mathbb{Z_m} 是一个完全剩余系，则 S = \{a, 2a \cdots ma\} 构成一个完全剩余系。

下面证明推论 2。

设集合 S = \{ra | r \in \mathbb{Z_m}\}。对于 r_i, r_j \in \mathbb{Z_m}, r_i \ne r_j。假设存在同余 r_i a \equiv r_j a (\bmod \ m)。由于 a \bot m，因此 r_i \equiv r_j(\bmod \ m)。根据完全剩余系的互异性，假设不成立。S 的互异性证明完成。

因为 S \subset \mathbb{Z}，由定义 (2) 可得，\forall a \in S，\mathbb{Z_m} 中有唯一的 r 满足 r \equiv a(\bmod \ m)。因此构成 S 对 \mathbb{Z_m} 的单射。又因为 |S| = |\mathbb{Z_m}|，故构成 S 到 \mathbb{Z_m} 的双射。

则对于任意整数，都存在 \mathbb{Z_m} 中的某个数 r 与之同余，亦存在 S 中某个数与之同余。定义 (1) 证明完成。因此 S 是一个完全剩余系。

简化剩余系

在完全剩余系基础上加上了更强的限制。

定义 \Phi_m = \{r_1, r_2 \cdots r_s\} 为模 m 的简化剩余系，当且仅当：

• 任意不同元素 r_i, r_j \in \Phi_m，都有 r_i \not \equiv r_j(\bmod \ m)。

• 其中定义 $(2), (3)$ 可以合并为 $\forall a \bot m$，都存在唯一的 $r \in \Phi_m$ 满足 $a \equiv r(\bmod \ m)$。 下面证明简化剩余系的一些推论。 > 推论 $1$：该剩余系对于 $\bmod \ m$ 的乘法具有封闭性。 证明：$\forall r_i, r_j \in \Phi_m$，都有 $r_i \bot m, r_j \bot m$。因此有 $r_i r_j \bot m$。根据性质 $(2), (3)$，$r_i r_j$ 也在 $\Phi_m$ 中。 根据 $a_i \bot m \to a_i \bot a_i ^ {-1}$ 可知，$a_i$ 的乘法逆元也在 $\Phi_m$ 中。因此证明了关于乘法和除法的封闭性，还证明了逆元的存在。 事实上，该简化剩余系 $\Phi_m$ 构成关于模 $m$ 乘法运算的交换群（阿贝尔群）。 > 推论 $2$：$\varphi(m) = |\Phi_m|$。 > 推论 $3$：对于 $m > 2$，有： > $$\sum _{r \in \Phi_m} r = 0$$ 证明：可能算是感性证明。根据欧几里得算法的流程，$(r, m) = 1$，则 $(m, m - r) = 1$，也即 $(m, -r) = 1$。因此，如果 $r$ 在 $\Phi_m$ 中，则 $-r$ 也在 $\Phi_m$ 中。由于 $r$ 与 $-r$ 模 $m$ 不相等，因此简化剩余系中的数总是成对出现。相加可以证明。 这也说明，简化剩余系 $\Phi_m$ 的大小 $|\Phi_m|$ 一定是偶数（$m > 2$）。 > 推论 $4$：若 $a \bot m$ 且 $\mathbb{\Phi_m}$ 是一个完全剩余系，则 $S = \{ra | r \in \Phi_m\}$ 构成一个完全剩余系。 证明方法可以参考完全剩余系性质 $2$ 的证明。

欧拉定理

定义：若 n, a 均为正整数，且 n 与 a 互质，则有 a ^ {\varphi(n)} \equiv 1(\bmod \ n)。

证明：对于 n 的简化剩余系 \Phi_n，根据简化剩余系的推论 4 可知，S = \{ar | r \in \Phi_n\} 也构成模 n 的简化剩余系。

根据 \prod_{r \in \Phi_n} r \equiv \prod_{r \in S} r (\bmod \ n)，有 a^{|\Phi_n|} = a ^ {\varphi(n)} \equiv 1 (\bmod \ n)。证毕。

由此可以得到更弱的定理 Farmet 小定理：\forall p \in \mathbb{P}，a^{p - 1} \equiv 1 (\bmod \ p)。

扩展欧拉定理

扩展欧拉定理的证明就不在我能力所及的范围内了。在这就放个结论吧。

这个柿子就比较有用了，可以用来搞降幂之类的事情。

欧拉降幂模板代码

例题

1. P4139 上帝与集合的正确用法

求 2 ^ {2 ^ {2 ^ {\cdots ^ {2}}}} \bmod p 的值。

设 f(p) 表示 2 的幂塔对 p 取模的值。那么他就等于 2 ^ {f(\varphi(p)) + \varphi(p)}。由于 \varphi 函数下降速度极快（\log 速度），很快 \varphi(p) 降为 1。这个东西可以递归求解。

int solve(int p) {
    if (p == 1) return 0;
    int phi = get_phi(p);
    int s = solve(phi);
    return qpow(2, s + phi, p);
}

2. CF906D Power Tower

给定一个数列 w_1, w_2 \cdots w_n 和模数 p, 每次询问一个区间 [l,r]，求 w_l ^ {w_{l + 1} ^ {w_{l + 2} ^ {{\cdots}^{w_r}}}} \bmod\ p 的值

考虑欧拉降幂。欧拉函数下降速度很快，O(\log p) 次就能降为 1。因此可能只需要计算到 w_{l + k}，后面的就全模 1 了（当然模 1 就是 0）。这个 k 是 O(\log p) 级别的。

上面讨论的都是幂次大于 \varphi(p) 的情况。如果幂次小于 \varphi(p) 呢？怎么提前判断掉呢？

如果数列的每一项都 \ge 2，那么可以直接暴力判断，因为 O(\log p) 个数乘起来就会达到 p。但是如果存在 1 呢？这个也好办，直接把 r 调到 l 后边的第一个 1 前面就行，这样保证了 [l, r] 中没有 1。同时，这个 1 对答案也没有影响，因为 x ^ 1 = x, 1 ^ x = 1。

下面是一份可供参考的代码实现：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define int long long

using namespace std;

const int N = 100010;
int n, m, p, a[N], suf[N];
map<int, int> bin;
int qpow(int a, int b, int p) {
    int s = 1; for (; b; b >>= 1, a = a * a % p)
        if (b & 1) s = s * a % p; return s;
}
bool check(int a, int b, int p) {
    int s = 1;
    for (; b; b >>= 1, a = a * a) {
        if (a >= p) return 0;
        if (b & 1) {
            s = s * a; if (s >= p) return 0;
        }
    } return 1;
}
int get_phi(int n) {
    int s = n; 
    for (int i = 2; i <= n / i; i ++ ) if (!(n % i))  {
        s = s / i * (i - 1); while (!(n % i)) n /= i;
    } if (n != 1) s = s / n * (n - 1); return s;
}
int solve(int u, int r, int p) {
    if (u == r) return a[u] % p;
    if (p == 1) return 0;
    int phi = bin[p], s = a[r]; bool flg = 0;
    for (int i = r; i > u + 1; i -- ) {
        if (!check(a[i - 1], s, phi)) { flg = 1; break; }
        s = qpow(a[i - 1], s, phi);
    } if (s >= phi) flg = 1; int pw;
    if (flg) pw = solve(u + 1, r, phi) + phi;
    else pw = s;
    return qpow(a[u], pw, p);
}
signed main() {
    scanf("%lld%lld", &n, &p);
    for (int i = 1; i <= n; i ++ )
        scanf("%lld", &a[i]);
    scanf("%lld", &m); int t = p; bin[1] = 1;
    while (t != 1) bin[t] = get_phi(t), t = bin[t];
    suf[n + 1] = n + 1;
    for (int i = n; i >= 1; i -- )
        if (a[i] == 1) suf[i] = i;
        else suf[i] = suf[i + 1];
    while (m -- ) {
        int l, r; scanf("%lld%lld", &l, &r);
        r = min(r, suf[l]); printf("%lld\n", solve(l, r, p));
    } return 0;
}