扩展欧几里得

1.裴蜀定理

对于关于x和y的线性不定方程（裴蜀等式）ax+by=c
当且仅当gcd（a，b）|c时有整数解，且有整数解时定有无穷多个整数解。

推论

a，b互质等价于ax+by=1有解

例题

luoguP4549

#include<bits/stdc++.h>
#define mo 100003
using namespace std;
int a[25],n;
int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}
int main(){
    scanf("%d",&n);
    cin>>a[1];
    for(register int i=2;i<=n;i++){
        cin>>a[i];
        if(a[i]<a[i-1]) a[i]=gcd(a[i-1],a[i]);
        else a[i]=gcd(a[i],a[i-1]);
    }
    cout<<max(a[n],-a[n]);
    return 0;
}

2.扩展欧几里得算法

应用

求ax+by=c的一组解/最小整数解
1.用扩欧求出一组特解

int exgcd(int a,int b,int &x,int &y){ 
if(b==0){
 x=1;y=0; return a; 
 }
else{
 int ret=exgcd(b,a%b,y,x); y-=x*(a/b); return ret; 
 }
 }

2.求最小解