数论中乘法逆元的几种求法

逆元

在离散数学中的概念自行查找资料吧

百度简单介绍一句

逆元一般指逆元素逆元素是指一个可以取消另一给定元素运算的元素，在数学里，逆元素广义化了加法中的加法逆元和乘法中的倒数。

先来引入取模（取余，两者差别不大）概念

(a + b) % p = (a%p + b%p) %p （对）

(a - b) % p = (a%p - b%p) %p （对）

(a * b) % p = (a%p * b%p) %p （对）

(a / b) % p = (a%p / b%p) %p （错）

为什么除法错的

证明是对的难，证明错的只要举一个反例

(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0

对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，我们是不是对这个算式就无法计算了呢？

答案当然是 NO (>o<)

这时就需要逆元了

a*x = 1 (mod p) 满足a乘以x对p取模等于1 此时称 x为a对p的逆元

只有a与p互质才有逆元互质公约数只有1 最大公约数为1

费马小定理

a^(p-1) ≡1 (mod p)

变形 a*a^(p-2) ≡1 (mod p)

此时 a^(p-2)就是a对p的逆元

 1 LL pow_mod(LL a, LL b, LL p)   //用到快速幂的知识，函数返回a的b次方对p取模
 2 { 
 3     LL ret = 1;
 4     while(b)
 5     {
 6         if(b & 1) 
 7             ret = (ret * a) % p;
 8         a = (a * a) % p;
 9         b >>= 1;
10     }
11     return ret;
12 }
13 LL Fermat(LL a, LL p)          //返回a对p的逆元
14 { 
15         return pow_mod(a, p-2, p);
16 }

扩展欧几里得

这个解的x就是a关于b的逆元，y就是b关于a的逆元

证明两边同对b取模

a*x % b + b*y % b = 1 % b

a*x % b = 1 % b

a*x = 1 (mod b)

所以x是a关于b的逆元反之可证明y

 1 void exgcd(LL a, LL b, LL &x, LL &y, LL &d)  //欧几里得函数
 2 {
 3     if (!b) 
 4         {d = a, x = 1, y = 0;}
 5     else
 6     {
 7         exgcd(b, a % b, y, x, d);
 8         y -= x * (a / b);
 9     }
10 }
11 LL inv(LL t, LL p)                    //返回t对p的逆元
12 {
13     LL d, x, y;
14     exgcd(t, p, x, y, d);
15     return (x % p + p) % p;        //x可能为负，也可能过大
16 }

递推方法

1 LL inv(LL t, LL p) //求t关于p的逆元，注意:t要小于p，最好传参前先把t%p一下
2 {
3     return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
4 }

推荐博客值得看 http://www.cnblogs.com/linyujun/p/5194184.html

https://oi.men.ci/mul-inverse/

菜鸡一枚欢迎大佬纠错