一：前置知识点
a:欧几里得算法：
1：欧几里得算法欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。
2：欧几里得算法证明：
两个引理：
若d是a和b的公约数，那么d也是b和c的公约数（c=a%b）若d是b和c的公约数（c=a%b），那么d也是a和b的公约数
按照辗转相除法如此循环下去，每次的余数r小于除数n ，那么相当于每次的被除数（变为上次的的除数）变小了，除数也变小了，而公因数的集合一直都没有变，也就是被除数和除数越来越小，而二者所包含的公共公因数又不变这样循环下去，最后除数就会变为最大公因数3：代码模板
int gcd(int a ,int b){return b ? gcd(b,a%b ) : a ;}
b: 倍祖定理
任意两个整数a,b,最大公约数为d=gcd(a,b),那么对于任意的整数x,y，ax+by=m,构成的m一定是d的整数倍(即m%d=0)
二：扩展欧几里得初识：
扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
ax + by = gcd(a,b)
如果a是负数，可以把问题转化成|a|(-x)+by = gcd(|a|,b)，然后令x'=(-x)。
通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)。
有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。
三：扩展欧几里得的应用：
1：求二元一次线性方程的整数解
扩展欧几里得算法的描述是：一定存在整数 x, y 满足等式 a * x + b * y = gcd(a,b)
所以扩展欧几里得算法可以计算出最大公因数gcd（a，b），又可以为计算出x，y的一组特解，如何求解呢
带入等式：gcd（b,a%b） = bx1 + (a%b)*y1gcd（b,a%b） =b*x1+(a-(a/b)*b)*y1gcd(b,a%b) = a*y1 + b*(x1-(a/b)*y1)当b不等于0时，gcd（a，b） = gcd（b，a%b）；所以 x= y1 ; y = x1 - (a/b) *y1 ;
根据这个过程，我们可以递归求解，那退出条件是什么呢，我们可以看到当b==0 是，求出公约数
，当b==0 是，a*x = gcd（a，0） = a ，此时，x==1 ，y等于0可以计算出一组特解
代码模板：
//求x，y 使得ax + by = gcd(a,b) ;int exgcd(int a , int b , int &x ,int &y){if(!b){x=1 ; y = 0 ;return a ; }int d = exgcd(b,a%b,x,y);int temp = y ;y= x-(a/b)*y ; x= temp ; return d ; }
2: 乘法逆元
这里先说一下乘法逆元，我们都知道，‘取模%’ 具有加、减、乘法的分配率即：
1). (a+b) % c = ((a%c) + (b%c))%c
2). (a-b) % c = ((a%c) - (b%c))%c
3). (a×b) % c = ((a%c)× (b%c))%c
这样的好处就是，如果a+b+…+n计算出来的值太大的话，可以通过分配率来计算出每一步的值在求余。
除法没有分配率，但是有乘法逆元。就是将除法转化为乘法。
逆元：设c是b的逆元，则有ax ≡ 1(mod p)；
(a/b)mod p = (a/b) * 1(mod p) = (a/b)bx (mod p) = ax(mod p)
定理：a存在模p的乘法逆元的充要条件是gcd(a,p) = 1;（定理的证明在这里就不叙述了）
对于ax + by = 1，可以看出x是a模b的乘法逆元，y是b模a的乘法逆元。
四：题目练习
同余方程（传送门）
题目描述：求关于xx的同余方程ax≡1(modb)的最小正整数解。
输出格式
一个正整数x_0x0，即最小正整数解。输入数据保证一定有解。
输入输出样例
输入 #1复制
3 10
输出 #1
7
分析
板子题，唯一需要做的就是转化一下将ax ≡ 1( mod b ) 变为 ax - by = 1 的形式，最后由于输出最小的正整数，我们调整一下即可
#include <bits/stdc++.h>using namespace std ;int a,b ,x,y,k; void exgcd (int a, int b ){if(!b){x=1 ; y = 0 ;return ; }exgcd(b,a%b);int temp = y ;y= x-(a/b)*y ; x= temp ; return ; } int main(){cin >> a>>b ; exgcd(a,b) ; cout << (x+b)%b << endl ; }
五：注意：
如果需要求该方程的最小非负整数解，该如何调整？
容易发现 a x + b y = g c d ( a , b ) ，等价于a ∗ ( x − k ∗ b ) + b ∗ ( y + k ∗ a ) = g c d ( a , b )
所以对于x的调整为x=(x%b+b)%b
对于y的调整为y=(y%a+a)%a
