用费马小定理和快速幂算法，求 a 在模 p 下的乘法逆元。
注意：这里的 p 必须为质数。
// 爱码岛编程
#include <iostream>
using namespace std;
// 快速幂算法（取模）：a^b % p
long long pow_mod(long long a, long long b, long long p) {
long long result = 1;
a %= p;
while (b) {
if (b & 1) // b % 2 == 1
result = (result * a) % p;
a = a * a % p;
b >>= 1;
}
return result;
}
// 求a在模p下的乘法逆元。（费马小定理，p必须为质数）
long long inv(long long a, long long p) {
return pow_mod(a, p - 2, p);
}
int main() {
long long a=7, p=13;
//费马小定理
cout << pow_mod(a, p-1, p) << endl;
// 逆元
cout << a << "在模" << p << "下的乘法逆元是：";
cout << pow_mod(a, p-2, p) << endl;
return 0;
}