什么是逆元?
逆元存在的条件是在取模运算中,一个数的逆元和该数乘积取模后的结果为1,即ax≡1(mod p),称x为a关于p的逆元,其中gcd(a,p)=1。
什么是逆元?a∗x≡1modm,这里x就是a的逆元。逆元有什么用呢?*如果我们要求a/bmodm的值,而a,b很大,设b的逆元为x,这个时候注意到(a/b)∗x∗b=(a/b)modm=a∗xmodm巧妙地把出发转换成了乘法
逆元求法
- 扩展欧几里得算法O(logn)
裴蜀定理:若a,b是整数,且gcd(a,b)=d,那么对于任意的对任意整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。(a,b互质的充要条件是存在整数x,y使ax+by=1.)
代码:x为a的逆元void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1,y=0;return ;} exgcd(b,a%b,x,y); ll z=x; x=y; y=z-y*(a/b); return ; }
如果gcd(a,b)=1时,对公式两边同时取模b,则有ax≡1(mod b),所以x为a关于模b的逆元。 - 费马小定理
- 线性求逆元