逆元

2019-04-13 15:07发布

站内文章 / 模拟电子
12506 0 1791
逆元（inv）1.什么是逆元当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：设c是b的逆元，则有b*c≡1(mod m)；则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);即a/b的模等于a*b的逆元的模；逆元就是这样应用的；
2.求逆元的方法(1).费马小定理在是素数的情况下，对任意整数都有。 
如果无法被整除，则有。 
可以在为素数的情况下求出一个数的逆元，，即为逆元。题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦。复杂度O(logn)；代码：[cpp] view plain copy
  1. const int mod = 1000000009;  
  2. long long quickpow(long long a, long long b) {  
  3.     if (b < 0) return 0;  
  4.     long long ret = 1;  
  5.     a %= mod;  
  6.     while(b) {  
  7.         if (b & 1) ret = (ret * a) % mod;  
  8.         b >>= 1;  
  9.         a = (a * a) % mod;  
  10.     }  
  11.     return ret;  
  12. }  
  13. long long inv(long long a) {  
  14.     return quickpow(a, mod - 2);  
  15. }  

(2)扩展欧几里得算法求逆元扩展欧几里得算法可以参考小白书；百度百科-乘法逆元中有这样一个例子:例如：4关于1模7的乘法逆元为多少？4X≡1 mod 7

热门文章