想看详细证明的:/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