python/TangDou/AcWing/NumberTheory/逆元/费马小定理+快速幂求逆元.md

模是质数求逆元

如果$a \times b=1(mod\ p)$，则$a$为$b$互为mod $p$逆元,其中$p$是质数。

根据费马小定理得

\large a^{p-1}\equiv 1 (mod \ p) \large \Rightarrow a \times a^{p-2} \equiv 1 (mod \ \ p )

所以，$a$和$a^{p-2}$互为 (mod \ \ p ) 逆元。

为了理解快速幂思想，先看一个例子：求5 ^ {19} = ? 因为$$19_{(10)} = 10011_{(2)}$$，所以有5 ^ {19} = 5 ^ {(1+2+16)} = 5^1 * 5^2 * 5^{16},将二进制分解思想实现。

快速幂代码

#include <bits/stdc++.h>
using namespace std;

int normal_pow(int a, int p) {
    int ans = pow(a, p); //普通幂
    return ans;
}

//递归版本的快速幂
int qpow_1(int a, int p) {
    if (p == 0)
        return 1;                    //任何数的0次方都是1,递归出口
    else if (p & 1)                  //如果p是奇数
        return qpow_1(a, p - 1) * a; //结果=qpow_1(a,p-1)*a，相当于用小一级的数字进行描述，形成递归
    else {
        int t = qpow_1(a, p / 2); //如果p是偶数,分治，结果相乘
        return t * t;
    }
}

//循环版本的快速幂,利用二进制思想进行8 4 2 1方式计算，达到logN的时间复杂度
int qpow_2(int a, int p) {
    int ans = 1;
    while (p) {
        if (p & 1) ans *= a;
        a *= a;
        p >>= 1; //缩小一半
    }
    return ans;
}

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << normal_pow(2, i) << endl;
        cout << qpow_1(2, i) << endl;
        cout << qpow_2(2, i) << endl;
    }
    return 0;
}

数论题目中的快速幂

typedef long long LL;
// 快速幂 (a^k)%p
LL qmi(LL a, LL k, LL p) {
    LL res = 1;                            
    while (k) {                             
        if (k & 1) res = res * a % p;  
        k >>= 1;                            
        a =  a * a % p;                 
    }
    return res;
}

快速幂求逆元

$normal_pow$是普通的求幂，$qpow_1$是递归方式实现快速幂，$qpow_2$用循环的方式实现快速幂，求逆元即求$qpow_1(a, p-2)$或qpow\_2(a, p-2)