拓展欧几里得算法：
1、模板：https://www.cnblogs.com/ydUESTC/p/16676229.html
2、原理：
3、应用：拓展欧几里得算法解线性同余方程：
4、例题：
（1）线性同余方程：
https://www.acwing.com/problem/content/205/
（2）含负数的ExGCD应用：
https://www.acwing.com/problem/content/224/
注意，（1）和（2）中都要求得最小正整数解，可以发现，在得到特解、通解过后，得到一个正余数即可。
即对特解x1、通解x：x = x1 + k * b / gcd(a, b)
求出x1对b/gcd(a,b)的正余数。（由于b/gcd(a,b)可能为负，故取模时需要取绝对值，并且需要取正余数的处理，详见（2））
标签：www,gcd,欧几里得,AcWing,算法,x1,同余 From： https://www.cnblogs.com/ydUESTC/p/16751176.html