逆元（b/a）%m的计算

逆元就是同余式中一个值为1的一种特殊情况

证明逆元
此处需要一个证明过程 （懒得写 ）

注意一点 要满足gcd(a,m)==1成立 并且 b%a==0

exgcd算法

#include<iostream>
#include<algorithm>
using namespace std;
int exGcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int g=exGcd(b,a%b,x,y);
	int temp=x;
	x=y;
	y=temp-a/b*y;
	return g;
}
int inverse(int a,int m){//求解ax+my=1 
	int x,y;
	int g=exGcd(a,m,x,y);
	return (x%m+m)%m;//a膜m的逆元 最小正整数解 
}
int main(){//(b/a)%m求解 	
	return 0;
}

求多个数的逆元打表效果更佳

板子

LL inv[mod+5];
void getInv(LL mod)
{
    inv[1]=1;
    for(int i=2;i<mod;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}