乘法逆元模板

2019-04-13 16:45发布

我们知道,在模意义下,加减乘运算是封闭的; 例如在模17意义下,8+11=((8%17)+(11%17))%17=2,19+21=((19%17)+(21%17))=6; 减法同理,但是在C++编译器中取模的意义是与数学上不同的,负数mod正数应该是非负数,但是C++却可能模出负数,所以我们要多加一些处理,对于x,可以(x%mod+mod)%mod保证其正确性,比如在模17意义下,21-19=((21%17)-(19%17))=2,35-21=((35%17)-(21%17))=14. 乘法也是这样,先模再乘,乘完再模,其意义不会变化。 但是除法不是。 于是我们需要用到除法逆元。 关于逆元的定义。 定义 对a∈Zm,存在b∈Zm,使得a+b ≡ 0 (mod m),则b是a的加法逆元, 记b= - a。
定义 对a∈Zm,存在b∈Zm,使得a×b ≡1  (mod m),则b为a的乘法逆元  ,记b=1/a; 加法逆元很少用啊,那么怎么求乘法逆元呢? 方法一:我们要找到a×b ≡1  (mod m)的b,所以很容易想到用扩展欧几里得求出a*b+m*y=1的一组解,b就是a在模m意义下的乘法逆元。当然前提是a与m互质,因为只有这样gcd(a,m)才是1 ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); ll t=y; y=x-(a/b)*y; x=t; return r; } ll inv(ll a) { ll x,y; ll r=exgcd(b,mod,x,y); if(r==1) return (x%mod+mod)%mod; return -1; }
方法二:根据费马小定理,a^(p-1)≡ 1(mod p)  所以稍加变形,a*a^(p-2)≡ 1(mod p)  即a^(p-2)是a在模p意义下的乘法逆元。 快速幂一下就好了,复杂度O(log p) 方法三:O(n)线性预处理 inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;可以再推一遍求出阶乘的逆元。

求出逆元之后,要求(a/b)%mod, 设b`为b在模mod意义下的逆元,直接(a%mod*b`%mod)%mod即可。