摘要：为什么引入乘法逆元？乘法逆元的定义将除法转换为乘法，就可以用分配律将大数拆成小数再取模问：如何求乘法逆元x呢？方法：费马小定理，扩展欧几里得，线性递推等乘法逆元费马小定理证明费马小定理举例代码实现#includetypedeflonglongll;//快速幂取模llfast_pow(lla,llb,llp){//a^b%pllans=1;while(b){if(b&1){//若b是奇数(b%2==1),则ans单独乘a，b-=1变成偶数ans=(ans*a)%p;}a=(a*a)%p;b>>=1;//(b/=2)b减半}returnans;}//费马小定理求逆元x=a^(p-2)%p;(

摘要：为什么引入乘法逆元？乘法逆元的定义将除法转换为乘法，就可以用分配律将大数拆成小数再取模问：如何求乘法逆元x呢？方法：费马小定理，扩展欧几里得，线性递推等乘法逆元费马小定理证明费马小定理举例代码实现#includetypedeflonglongll;//快速幂取模llfast_pow(lla,llb,llp){//a^b%pllans=1;while(b){if(b&1){//若b是奇数(b%2==1),则ans单独乘a，b-=1变成偶数ans=(ans*a)%p;}a=(a*a)%p;b>>=1;//(b/=2)b减半}returnans;}//费马小定理求逆元x=a^(p-2)%p;(