扩展欧几里德求逆元+通用除法取模

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int e_gcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int gcd=e_gcd(b,a%b,y,x);
	y-=x*(a/b);
	return gcd;
}
int inv(int a,int m){
	int x,y;
	int d=e_gcd(a,m,x,y);
	if(d!=1)return -1;
	int ans=(x%m+m)%m;
	return ans;
}
int main(){
	int a,b,mod;
	cin>>a>>b>>mod;
	int ans=a*inv(b,mod)%mod;
	int reans=a%(mod*b)/b;//适用于所有的除法取模，不过mod*b过大可能数据溢出
	if(inv!=-1)
	cout<<ans<<endl;
	else 
	cout<<reans<<endl;
}

乘法逆元主要用于除法取模，而求取逆元最常用的方法就是扩展欧几里得。由于对于取模运算，我们要求必须是整数，故若是我们在类似于a/b%c这种除法取模运算不加以操作的话，有很大的可能性得到错误的结果，而乘法逆元总是能很好的解决这种情况。现在我们需要来了解一下什么是乘法逆元，当 a ≡ b (mod n) 的时候，我们称"a和b关于模n同余",即a mod n =b mod n,而当a*x ≡ 1 (mod n)的时候，我们称x为a关于模n的逆 ，它类似于实属运算中的"倒数"的概念。由于a*x与1关于模n同余，故a * x - 1 = n * y,我们移一下项可以得到，a * x - n * y = 1(注:这里的等号都是数学上的等号)。这个时候我们的任务就是求得方程里面x的值，而恰巧的是扩展欧几里德刚好能解这个形式的方程的解（对了，由于满足x ≡ y ( mod n)的其他整数解y也是方程的解，所以当我们谈到同余方程的一个解时，其实指的时一个同余等价类。对于a *x ≡ 1(mod n)而言，当gcd(a,n)=1时，该方程有唯一解)。乘法逆元的概念大致就这样(对了，由于是一个同余等价类，我们要将最小的非负整数解作为逆元，即逆元在0~n-1之间)。

接下来，我们来了解一下扩展欧几里德是如何求得逆元的。首先，我们都明白一点的是，欧几里德能够通过辗转相除来求得a，b的最大公约数，其结束条件是b=0，当b=0时，a就是我们要求得的gcd(a,b),此时x=1，y=0(其实此时y可以是任意数，为了方便我将其记为0），我们不妨将x=1，y=0当作其最终状态，通过递归求解其初始状态，即方程的解。

对于a*x+b*y=gcd的下一个状态,b*x1+a%b*y1 = gcd，由于a%b =a-a/b * b,故gcd = b*x1+(a-a/b*b )*y1，化简得gcd = a*y1+b(x1-a/b*y1),通过这个式子我们可以得到其上个状态的x，y分别是x=y1,y=x1-a/b*y1。通过这样不断的逆推，最后我们就能够得到ax+by=gcd的一个特解，并且求出gcd(a,b）。以上就是我对扩展欧几里德的浅薄认识。

说了这么多，可能有些人还是没有理解为什么逆元能够解决除法取模的问题。

首先，明确我们的目标，我们要求的是a/b%c的值

然后，我们来分析一下b*x≡1(mod c)

易知，b*x≡1(mod c)的充要条件是b*x-1=c*y

能够解得b=(c*y+1)/x

将b带入到a/b%c中可得

a/b%c=a%c/[(c*y+1)/x]%c

又[(c*y+1)/x]%c=[(c*y+1)%c]/(x%c)

即[(c*y+1)/x]%c=1/(x%c)

综上可得a/b%c=(a%c)*(x%c)

即a/b%c=a*x%c

故我们可以用逆元来进行除法取模的运算(这个纯属自己推导的，有错误还望指出)

这种转换实在是太有意思了，很好的将除法取模转换成了乘法取模，避免了取模出错的可能。不过我们需要注意的一点是乘法逆元当且仅当a/b % c里的b和c互素时才存在。

对于b和c不互素的情况，我们可以采取更通用简便的情况来解决除法取模的问题

直接将求a/b mod c转换成a mod (c*b)/b

(a/b) mod c=a mod (c*b)/b证明过程

不妨设

a/b=k*c+x;x=(a/b) mod c;

a=k*b*c+b*x;

a mod (b*c)=b*x;

a mod (b*c)/b=x;

因x=(a/b) mod c,故可得到

a mod (b*c)/b=(a/b) mod c;

证毕。

在下蒟蒻一枚，有任何错误欢迎指出

扩展欧几里德求逆元+通用除法取模

推荐阅读