一、欧几里得算法
1.简介
欧几里得算法又称辗转相除法，这种算法我们在高中的数学书上都有所了解，这种算法的用途是旨在求两个数的最大公约数(英文缩写为gcd)。
2.算法分析
例如，如果我们要求去寻找12和16的最大公约数，我们可以这样操作：
第一步：16 mod 12 = 4；
第二步：12 mod 4 = 0；
第三步：4 mod 0，这时候b==0的时候，a==4就是我们12和16的最大公约数。
3.代码分析
int gcd(int a,int b)
{
??? return !b?a:gcd(b,a%b);}
代码的长度其实很简单，就是判断b是否为0，如果为0，返回a，否则递归寻找。
二、扩展欧几里得算法
1.简介
何为扩展欧几里得算法？扩展欧几里得算法顾名思义就是欧几里得算法的扩展。这个算法旨解决一个问题：求，其中a,b为常数，gcd(a,b)为a,b的最小公倍数 的整数解(可以拥有多个整数解)。
2.算法分析
求解特殊情况：
首先我们要知道裴蜀定理，就是一定会有整数解。
由欧几里得算法可知;......①
若b=0时，则，x=1，令y=0；
若a≠0时，则成立；......②
即......③
将①②③联立得
这样，我们可以用递归的形式来求得x和y的值。
void exgcd(int a,int b,int &x,int &y){
?? ?if(b==0){
?? ??? ?x=1;
?? ??? ?y=0;
?? ?}
?? ?exgcd(b,a%b,y,x);
?? ?y=y-a/b*x;
}
求解一般情况：()
由裴蜀定理可知，若有解，则必然满足
令,则我们可以先求
的解，然后得到x,y的值
其中x,y都是特解。
而非齐次通解=非齐次的特解+齐次通解则，我们只需要求的通解。
即,带入得到
3.代码分析
例题引入：AcWing 878. 线性同余方程
例题分析：可以化为
即可以化为//因为k仅仅只是个常数，所以可以不变号
这样就是求x和k的整数解的题了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
void exgcd(long long a,long long b,long long &x,long long &y){
if(b==0){
x=1;
y=0;
return;
}
exgcd(b,a%b,y,x);
y=y-a/b*x;
}
long long gcd(long long a,long long b){
return !b?a:gcd(b,a%b);
}
int main(){
long long t;
cin>>t;
while(t--){
long long a,b,m;
cin>>a>>b>>m;
long long sum=gcd(a,m);
if(b%sum!=0){
cout<<"impossible"<<endl;
}
else{
long long x=0,y=0;
exgcd(a,m,x,y);
cout<<x%m*(b/sum)%m<<endl;//直接乘以b/gcd(a,b)即可
}
}
return 0;
}关于求解最小正整数解的时候，只需要 x=(×％t+t)%t，t=b/gcd(a,b);
同理，y=(y%t+t)%t,t=a/gcd(a,b);
?
