摘要：为什么引入乘法逆元？乘法逆元的定义将除法转换为乘法，就可以用分配律将大数拆成小数再取模问：如何求乘法逆元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;(

参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c算术基本定理证明  定理2-2（算术基本定理）：任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer。其中，p1...pr是互不相同的素数，e1...er是正整数.  存在性（任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer）证明：n=1：n是0个素数的乘积，存在性成立.n>1:假设所有小于n的正整数都可以表示成素数的乘积。对于n，分两种

参考资料：1.https://www.bilibili.com/video/BV1x3411s7Sy/?spm_id_from=333.788&vd_source=e66dd25b0246f28e772d75f11c80f03c算术基本定理证明  定理2-2（算术基本定理）：任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer。其中，p1...pr是互不相同的素数，e1...er是正整数.  存在性（任何非零整数n可以表示出如下乘积形式：n=±p1e1...prer）证明：n=1：n是0个素数的乘积，存在性成立.n>1:假设所有小于n的正整数都可以表示成素数的乘积。对于n，分两种