『算法-ACM 竞赛-数学-数论』逆元（拓展欧几里得）模板

ACM 常用模板合集

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int r=exgcd(b,a%b,x,y);
	int t=y;
	y=x-(a/b)*y;
	x=t;
	return r;
}
int main()
{
	//m=A%mod n与mod互质 求解(A/n)%mod
	long long m,n,mod;
	cin>>m>>n>>mod;
	long long ans,tem;
	exgcd(n,mod,ans,tem);
	ans=(ans+mod)%mod;
	cout<<(ans*m)%mod<<endl;
}