同余-乘法逆元-费马小定理

同余：

如果两个整数$a,b$模$m$的余数相同，则$a,b$模$m$同余$a \equiv b(\bmod m)$ LaTex公式为a \equiv b(\bmod m)

乘法逆元：

如果$a,b$互质，且满足$ax \equiv 1(\bmod b)$,则称$x$为$a$模$b$的乘法逆元

费马小定理

若$p$是质数，且$a,p$互质，则$a^{p-1} \equiv 1 (\bmod p)$,例如$4^{3-1} \equiv 1 (\bmod 3)$ 由费马小定理得：$a*a^{p-2} \equiv 1(\bmod p)$,则$a^{p-2}$是$a^p$的乘法逆元

代码

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;

int qmi(int a,int b,int p){
    int res=1;
    while (b){
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    int a,p;
    cin>>a>>p;
    if (a%p) pr(qmi(a,p-2,p))

    return 0;
}