乘法逆元

乘法逆元

乘法逆元在模算术中具有举足轻重的地位，(OI)中随处可见它的身影，是一个(OIer)必不可少的基础技能。

对于乘法逆元的作用，我觉得这个总结的挺好：

乘法逆元，一般用于求

[frac{a}{b}pmod{p} ]

的值，是解决模意义下除法运算的重要手段。

那么问题来了，为啥不直接除呢？原因是除法不满足模意义下的运算规则，我们要把它转换成乘法的形式。

乘法逆元定义

如果有一个线性同余方程(axequiv 1pmod{p})，且(a,p)互质，则(x)称为(amod p)的逆元，记作(a^{-1} mod p)。

回到这个式子

[frac{a}{b}pmod{p} ]

我们求它就等于求

[ab^{-1}pmod{p} ]

求逆元的一般方法

扩展欧几里得求解线性同余方程

线性同余方程：给定整数(a,b,m)，求一个整数(x)满足(a*xequiv bpmod{m})，或给出无解。由于未知数次数为1，我们也称其为线性同余方程。其等价于求解方程(ax+my=b)，其中(y)为(-frac{ax-b}{m})。

显而易见，该方程可以用(Bezout)定理求解，由定理得其有解当且仅当(gcd(a,m)mid b)。具体做法就是求出特解(gcd(a,m))然后通分。

inline int exgcd(int a,int b,int &x,int &y)
{
	if(b==0){x=1,y=0;return a;}
	int d=exgcd(b,a%b,x,y);
	int z=x;x=y;y=z-y*(a/b);
	return d;
}

费马小定理

费马小定理：

[a^{p-1}equiv 1pmod{p} ]

其可以化为：

[a^{p-2}*aequiv 1 pmod{p} ]

根据乘法逆元的定义，(a^{p-2})即为(a)在模(p)意义下的逆元。通过快速幂我们就可以(O(logn))地求任意正整数的逆元。

线性求逆元

上面两种方法一般是计算单个正整数的逆元时使用，如果我们需要一堆数的逆元时，上面两种算法都显得很慢了。

对于一个正整数(p)，它可以被写作(kq+r)的形式，其中(q>r)。即(p=kq+r)，在模(p)的意义下，它记为(kq+requiv 0pmod{p})，移项得(-kqequiv rpmod{p})，两边同时乘上(q,r)的逆元，得到(-kr^{-1}equiv q^{-1}pmod{p})，把(r)和(k)替换成(p)，再变化一下，得到((p-frac{p}{q})(pmod q)^{-1}mod p = q^{-1})。

inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=(p-p/i)*inv[p%i]%p;