逆元（模板）

1.费马小定理

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ksm(int x,int y,int p){int ans=1;while(y){if(y&1) ans=ans*x%p;x=x*x%p;y>>=1;}return ans;
} 
signed main()
{//求 n 在 p 下的逆元，p 必须是质数int n,p;cin >> n >> p;cout << ksm(n,p-2,p);return 0;
}

2.扩展欧几里得

#include<bits/stdc++.h>
using namespace std;
#define int long long
void exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return ;}exgcd(b,a%b,y,x);y-=(a/b)*x;
}
signed main()
{//求 n 在 p 下的逆元，p 和 n 必须是互质的 int n,p,x,y;cin >> n >> p;exgcd(n,p,x,y);cout << (x%p+p)%p;return 0;
}

3.线性逆元

#include<bits/stdc++.h>
using namespace std;
#define int long long
int inv[200005]; 
signed main()
{//求 1~n 在 p 下的逆元，p 必须是质数 int n,p;cin >> n >> p;inv[1]=1;for(int i=2;i<=n;i++){inv[i]=-(p/i)*inv[p%i];inv[i]=(inv[i]%p+p)%p;}for(int i=1;i<=n;i++){cout << inv[i] << endl;}return 0;
}