You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
44 lines
948 B
44 lines
948 B
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
|
|
int exgcd(int a, int b, int &x, int &y) {
|
|
if (!b) {
|
|
x = 1, y = 0;
|
|
return a;
|
|
}
|
|
int d = exgcd(b, a % b, y, x);
|
|
y -= a / b * x;
|
|
return d;
|
|
}
|
|
|
|
// 快速幂 (a^k)%p
|
|
int qmi(int a, int k, int p) {
|
|
int res = 1;
|
|
while (k) {
|
|
if (k & 1) res = res * a % p;
|
|
k >>= 1;
|
|
a = a * a % p;
|
|
}
|
|
return res;
|
|
}
|
|
// https://blog.csdn.net/weixin_42759798/article/details/99451434
|
|
|
|
// 逆元（费马小定理法）
|
|
// https://blog.csdn.net/qq_45863710/article/details/107424938
|
|
|
|
// https://blog.csdn.net/f1932460873/article/details/81193462
|
|
int main() {
|
|
// 1、扩展欧几里得求逆元
|
|
// 5*7 mod 3 的逆元
|
|
|
|
//
|
|
int x, y;
|
|
exgcd(5 * 7, 3, x, y);
|
|
|
|
cout << (x + 3) % 3 << endl;
|
|
|
|
// 2、费马小定理求逆元使用场景
|
|
cout << qmi(5 * 7, 3 - 1, 3) << endl;
|
|
return 0;
|
|
} |