观前提醒：「文章仅供学习和参考，如有问题请在评论区提出」
前置
剩余类（同余类）
给定一个正整数 (n) ，把所有的整数根据模 (n) 的余数 (rin [0, n - 1]) 分为 (n) 类，每一类就可以被表示为 (C_{r} = nx + r) 。那么这类数所构成的集合就称为模 (n) 的剩余类。
完全剩余系（完系）
给定一个正整数 (n) ，有 (n) 个不同的模 (n) 的剩余类（因为余数 (rin [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)) 。
欧拉定理
定义：若 (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) 的简化剩余系。所以
扩展欧拉定理
给定三个正整数 (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;
}
参考资料
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
