快速幂费马小定理求逆元

用费马小定理和快速幂算法，求 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;
}

经典算法

快速幂费马小定理求逆元