https://blog.csdn.net/qq_37174526/article/details/90112064
https://blog.csdn.net/BBHHTT/article/details/79792324
https://blog.csdn.net/zhjchengfeng5/article/details/7786595
#include <stdio.h> int ex_gcd(int a, int b, int *x, int *y) { if (!b) { //递归出口 *x = 1, *y = 0; return a; } int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy);// xx, yy保留上一层的 x 和 y值 参加 ax+by=gcd(a,b)的推导 *x = yy; // 当前层 x值等于上一层y(yy)值， y值等于上一层x值(xx)减a/b*上一层y值(yy) *y = xx - a / b *yy; return ret; } int main() { int a, b, x, y; while(scanf("%d%d",&a, &b) != EOF) { printf("ex_gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y)); printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b *y); } }
a*x=1( mod m) ,我们称 x 是 a 关于 m 的乘法逆元，等价于 a * x +m * y = 1; 当gcd( a , m ) != 1 时，无解。所以gcd( a , m ) = 1 是有解的充要条件，又扩展欧几里得算法，我们一般能找到无数解，题目一般会让输出最小的那组，我们可以得到一个特殊解x0（扩展欧几里德算法），x0 % m 就是最小解了。
因为：通解 x = x0 + m * t ; 也就是说 a 关于 m 的逆元是一个关于 m 同余的，那么一定存在一个最小正整数，它是 a 关于 m 的逆元，肯定在（0，m）之间，而且只有一个。
有时候由于问题的特殊性，我们得到的特解 x0 是一个负数（%与mod的不同），当 x0 为负数是，x0 mod m 结果仍为负（在计算机中用%代替mod的原因，注意%d,mod的区别），所以要对 x 稍加处理。
代码实现：要加上扩展欧几里德算法e_gcd(int a,int b,int &x,int &y)函数
例如： 5 是 5 关于 6的乘法逆元 5 * 5 % 6 = 1； 通解 是 5 + 6*t
int modReverse(int a,int m) { int x, y; int an s= e_gcd(a, m, x, y); if(ans == 1)//有解的充要条件 return (x % m + m) % m;//最小逆元，+m是将负数变为正数 else return -1;//无逆元 }
