总结 学了gcd，肯定得把exgcd学了，不然，我怎么学中国剩余定理。
证明 O（ log n ） 前提条件：d==gcd(a,b)
问题：ax+by=d,求x和y的通解
那么我们先建立一个方程组
A：ax1 + by1= d ==gcd(a,b)
B：bx2 + a%by2= d ==gcd(b,a%b)
B方程式展开：bx2 + ( a - a / b * b ) * y2=d
括号打开再合并：ay2 + b * ( x2 - a / b * y2 ) = d
所以：
x1=y2
y1=x2 - a / b * y2
不断递归下去到头
ax + 0*y = gcd(a,0);
所以x=1,y=0;
ax+by=c
如果 d | c 一定有解，否则一定无解
注意1：
exgcd求得是c == d的x,y
x= x * c/d, y = y * c/d;
这里才是正式的ax+by=c的x与y的一组解。
【板子|扩展欧几里得算法证明（exgcd）】注意2：
exgcd求到得x，可能为负数，所以不断得加最小系数k1和减去k2
a * （ x + k1 ）+ b * ( y - k2 )=d
展开后，保证a * k1==b * k2 == lcm(a,b)
所以 k1= lcm(a,b) / a , k2 = lcm(a,b)/b;
然后加成正数就行，但是不是最小正数，x>=k1，就得不断减去k1
代码
///第一步：先求exgcd的，x,y
///第二步：看是否需要加系数k1,k2
int exgcd(int a,int b,int &x1,int &y1)///求到c==gcd的一个x与y的解
{
if(b==0)
{
x1=1,y1=0;
return a;
}
int x2,y2;
int gcd=exgcd(b,a%b,x2,y2);
x1=y2,y1=x2-a/b*y2;
return gcd;
}
x=(x%k1+k1)%k1;
///这一步才是最小的正整数x，x>=k1，要降，x<0,要增加。
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。