1.关于扩展欧几里得算法的理解
首先要先学会欧几里得算法（辗转相除法）：
int gcd(int a, int b) {
?? ?return b ? gcd(b, a % b) : a;
}
/*
c = a % b;
a = b; b = c;
if b != 0 重复上述步骤
if b == 0 return a;
*/
然后去看扩展欧几里得算法：
几个关键点：
????????因为 ax + by = gcd(a, b)?
?? ??? ? ? ? ? ?bx1 + (a % b)y1 = gcd(b, a % b)
?? ??? ? ? ? ? ?gcd(a, b) = gcd(b, a%b)
?? ??? ? ? 所以 ax + by = bx1 + (a % b)y1
?? ??? ? ? 因为 a % b = a - b[a / b] ? ? ? ?(这里a / b是计算机的整除)
?? ??? ? ? 整理可得解为：
?? ??? ? ? x = y1;
?? ??? ? ? y = x1 - (a / b) * y1;
?? ??? ? ? 因为一开始只知道x和y，x1和y1是需要求的，那么我们根据上面发现的特性，发现需要从后往前不断求，
?? ??? ? ? 最后得出x和y，所以需要递归的思想。
?? ??? ? ? 递归出口是当b = 0时，x = 1，y = 0。(注意这里准确说是xn = 1，yn = 0)
?? ??? ? ? 此时x = 1，y = 0(即xn = 1，yn = 0)这个解就是最后的一组解，然后从后往前，不断的得出解，最后就得到了x和y的解
?? ??? ? ? 下面通过代码具体解释一下：
直观的代码：
void exgcd(int a, int b, int &d, int &x ,int ?&y)
//一开始从前往后不断递归的时候，其实只计算了a和b，int &x和int &y是从后往前返回的时候进行的相应赋值和计算
{
?? ?if ( !b )
?? ?{
? ? ? ? d = a;
?? ??? ?x = 1;
?? ??? ?y = 0; //这里是最后一组解(即xn = 1，yn = 0)
?? ??? ?return;
?? ?}
?? ?int x1,y1;
?? ?exgcd( b , a % b , d , x1 , y1 );
/*
这里x1和y1一开始从前往后递归时没有值，当从后往前返回时，得到了值（相当于得到了未来的值）然后通过下面的
x = y1;
y = x1 - ( a / b ) * y1;
这两行代码就得到了这层递归循环的x和y的值（即当前的值，但是当return返回后，又相当于上一层递归循环的未来的值）
?*/
?? ?x = y1;
?? ?y = x1 - ( a / b ) * y1;
?? ?return ;
}
简化的代码（不直观）：
int exgcd(int a, int b, int &x, int &y)
{
? ? if (!b)
? ? {
? ? ? ? x = 1; y = 0;
? ? ? ? return a;
? ? }
? ? int d = exgcd(b, a % b, y, x);
?/*
?这里是我认为比较难想的地方，不直观，下面讲讲我的理解：
这行代码里int d = exgcd(b, a % b, y, x);的y，x一开始从前往后递归时没有值，当从后往前返回时，
y的地方相当于x1的位置，x的地方相当于y1的位置，那么从后往前返回时，返回的值会给y和x赋值，
y得到了返回的x1的值，x得到了返回的y1的值，因为：
x = y1;
y = x1 - ( a / b ) * y1;
所以x不用变，y现在等于x1，x现在等于y1
所以y = y - ( a / b ) * x 就得到了当前这层递归循环y应该的值
这样一来，这层递归循环的x和y的值就都得到了
然后int exgcd(int a, int b, int &x, int &y)这里是x和y的实参，所以刚才得出的x和y的值，
就会传给这里的int &x, int &y，然后继续返回。
? */
? ? y -= (a/b) * x;
? ? return d;
}
2.下面介绍乘法逆元的理解：
1.乘法逆元的作用
当a和b过大时，要进行取模操作，可以如下操作，
（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 / b）% p 等同于 (a * b的逆元) % p, 那么问题转化为求b的逆元
设b的逆元为x，则 (b * x) mod p = 1
2.乘法逆元的条件
因为(b * x) mod p = 1
所以 b * x - n * p = 1
即 b * x + n * p = 1
通过前面的学习，我们知道b * x + n * p = k有整数解的条件是
k是gcd(b, p)的整数倍，所以k % gcd(b, p) = 0
当 k = 1 时，1 % gcd(b, p) = 0
所以gcd(b, p) = 1 ，即b 和 p互质是有乘法逆元的充要条件
3.如何求乘法逆元
我们发现b * x + n * p = 1 里的x可以用前面学过的扩展欧几里得算法得到，
求最小逆元就直接x % p就可以了（x 和 p此时都是正数）。
4.求乘法逆元的代码
int inv(int b, int p) {
?? ?int x, y;
?? ?int gcd = exgcd(b, p, x, y);
?? ?if(1 % gcd != 0)?? ?return -1; //没有乘法逆元
?? ?p = abs(p);
int ans = x % p;
if(ans <= 0) ans += p;
?? ?return ans;?
?? ?/*
?? ?防止x是负数，
?? ?x是负数时，x % p + p 得到正数解
?? */
}
|