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;
}
