欧拉定理 & 扩展欧拉定理

观前提醒:「文章仅供学习和参考,如有问题请在评论区提出」


前置


剩余类(同余类)


给定一个正整数 \(n\) ,把所有的整数根据\(n\) 的余数 \(r\in [0, n - 1]\) 分为 \(n\) 类,每一类就可以被表示为 \(C_{r} = nx + r\) 。那么这类数所构成的集合就称为\(n\) 的剩余类


完全剩余系(完系)


给定一个正整数 \(n\) ,有 \(n\) 个不同的模 \(n\) 的剩余类(因为余数 \(r\in [0, n - 1]\) )。

从这 \(n\) 个不同的剩余类中各取出一个元素,总共 \(n\) 个数,将这些数构成一个新的集合,则称这个集合为\(n\) 的完全剩余系

例如:\(n = 5\) 时,\(\{ 0, 1, 2, 3, 4 \}\)\(\{ 5, 1, -3, 8, 9 \}\) 都是一个模 \(5\) 的完全剩余系。

因为他们都有 \(5\) 个不同的模 \(5\) 的剩余类 \(r \in [0, 4]\)


简化剩余系(缩系)


给定一个正整数 \(n\) ,有 \(\varphi(n)\) 个不同的模 \(n\) 的余数 \(r\)\(n\) 互质的剩余类。

从这 \(\varphi(n)\) 个剩余类中各取出一个元素,总共 \(\varphi(n)\) 个数,将这些数构成一个新的集合,则称这个集合为模 \(n\) 的简化剩余系。

\(\varphi(n)\) 为欧拉函数,\(1 \sim n\) 中与 \(n\) 互质的数的个数。

例如:\(n = 5\) 时,\(\{ 1, 2, 3, 4\}\) 是一个模 \(5\) 的简化剩余系。\(n = 10\) 时,\(1, 3, 7, 9\) 是一个模 \(10\) 的简化剩余系。

显然,\(n\) 的简化剩余系中所有的数都与 \(n\) 互质


欧拉函数


\(1 \sim n\)\(n\) 互质的数的个数称为欧拉函数,记作 \(\varphi(n)\)

\[\begin{align} n = p_{1}^{a_{1}} p_{2}^{a_{2}} p_{3}^{a_{3}} ... p_{k}^{a_{k}}\\ \varphi(n) = n \times {\textstyle \prod_{i = 1}^{k}} \frac{p_{i} - 1}{p_{i}} \end{align} \]


欧拉定理


定义:若 \(\gcd(a, n) = 1\) ,则 $a^{\varphi(n)} \equiv 1 \pmod{n} $ 。

证明

\(\{ r_{1}, r_{2},...r_{\varphi(n)}\}\) 是一个模 \(n\) 的简化剩余系。

那么 \(r_{i}\) 就是和 \(n\) 互质,又因为 \(\gcd(a, n) = 1\) ,所以 \(a\)\(n\) 也是互质的。

那么 \(\{ ar_{1}, ar_{2},...ar_{\varphi(n)}\}\) 也是一个模 \(n\) 的简化剩余系。所以

\[\begin{align} {\textstyle \prod_{i = 1}^{\varphi(n)}}r_{i} &\equiv {\textstyle \prod_{i = 1}^{\varphi(n)}} ar_{i} \pmod{n} \\ {\textstyle \prod_{i = 1}^{\varphi(n)}}r_{i} &\equiv a ^{\varphi(n)}{\textstyle \prod_{i = 1}^{\varphi(n)}} r_{i} \pmod{n} \\ a ^{\varphi(n)} &\equiv 1 \pmod{n} \\ \end{align} \]


扩展欧拉定理


\[a^{b} = \begin{cases} a ^ {b}&, b < \varphi(m), \mod (m)\\ a ^ {b \mod \varphi(m) + \varphi(m)}&, b\ge \varphi(m), \mod(m) \end{cases} \]


P5091 【模板】扩展欧拉定理 - 洛谷

给定三个正整数 \(a, b, m\) ,求 \(a ^ b \mod m\)

\(1 \le a \le 10^9, 1 \le m \le 10^9, 1 \le b \le 10^{20000000}\)

可以根据扩展欧拉定理,当 \(b < \varphi(m)\) 时,用快速幂求解,当 \(b \ge \varphi(m)\) 时,通过定理进行降幂,然后再用快速幂求解。

实现代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

// 快速幂, a ^ k % p
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 求 n 的欧拉函数
int get_phi(int n) {
    int res = n;
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            res = res / i * (i - 1);
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

// 对 b 进行降幂
int de_pow(string s, int phi) {
    int res = 0;
    bool flag = false;
    for (int i = 0; s[i]; i++) {
        res = res * 10 + s[i] - '0';
        if (res >= phi) flag = true, res %= phi;
    }
    if (flag) res += phi;
    return res;
}

int main() {
    int a, m;
    string b;
    cin >> a >> m >> b;

    int phi = get_phi(m);
    int B = de_pow(b, phi);
    cout << qmi(a, B, m) << "\n";

    return 0;
}

参考资料


522 剩余系 欧拉定理 扩展欧拉定理_董晓算法

热门相关:有个人爱你很久   买妻种田:山野夫君,强势宠!   买妻种田:山野夫君,强势宠!   不科学御兽   不科学御兽