想看详细证明的：/hadilo/p/5914302.html
扩展欧几里得算法，简称 exgcd，一般用来求解不定方程，求解线性同余方程，求解模的逆元等，本篇只给出解不定方程ax+by=c;
定理1： 如果a和b都是整数，则有整数x 和整数y 使得 ax+by=gcd(a,b);(Bezout定理)
定理2：整数a,b互素当且仅当存在整数x,y使得ax+by=1;
定理3：a,b,c都是整数。如果c不是gcd(a,b)的倍数，则不定方程ax+by=c 没有整数解。如果c是gcd(a,b)的倍数，则有无穷多的解。如果（x0,y0）是ax+by=c的一个解，则ax+by=c的所有整数解是 ：x= x0+k*(b / gcd(a,b) )y= y0-k*(a / gcd(a,b) ); 其中k是整数。
给出模板：
#include<bits/stdc++.h>using namespace std;int exgcd(int a,int b,int &x,int &y){if(b==0) {x=1,y=0;return a;}int t=exgcd(b,a%b,x,y); //得到最大公约数t int x0=x,y0=y;x=y0;y=x0-(a/b)*y0;//得到通解 return t;}int main(){int a,x,y,b,c;cin>>a>>b>>c;//a,b,c; int t=exgcd(a,b,x,y);if(c%t!=0) cout<<"无解";else{printf("通解为：x= %d ,y= %d\n",x,y);cout<<"给出10组特解："<<endl;for(int i=-5;i<=5;i++){printf("(x=%d,y=%d) ",x+i*(b/t),y-i*(a/t));if(i==0) cout<<endl;} }return 0;}
例题 SGU 106
