目录观前提醒：「文章仅供学习和参考，如有问题请在评论区提出」
前置
剩余类（同余类）
给定一个正整数 \(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} \]
给定三个正整数 \(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;
}
参考资料
标签：剩余,int,res,定理,扩展,varphi,欧拉 From： https://www.cnblogs.com/oneway10101/p/17627733.html