即:gcd(a,b)=gcd(b,a%b)欧几里得算法在oi里非常常用,几乎每个数学题都有欧几里得算法——gcd。说白了就是求最大公约数。一行代码搞定:
int gcd(int a,int b){
return !b?a:gcd(b,a%b);
}
定理1:设a和n不全为0,则存在整数x,y,满足ax+by=gcd(a,b)。证明:当b=0时,gcd(a,b)=a。因为1\times a + 0 \times 0 =a,所以,ax+by=gcd(a,b)有一组解为x=1,y=0。当b \not = 0 时,gcd(a,b)=gcd(b,a%b)。设x’,y’满足gcd(a,b)=bx’+(a%b)y’=gcd(b,a%b)。那么,bx’+(a%b)y’=gcd(a,b)即,bx’+(a-(a/b)\times b )y’=gcd(a,b),其中’/‘为整除。所以,bx’+ay’-(a/b)\times b \times y’=gcd(a,b)即,ay’+b\times (x’-(a/b)\times y’)=gcd(a,b)那么可以继续递归拓展欧几里得:x=y’,y=(x’-(a/b)\times y’)。因为欧几里得算法的递归过程,可知定理1成立。证毕。
void Exgcd(int a,int b,int &d,int &x,int &y){
//求解ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b)。
if(!b) d=a,x=1,y=0;
else{
Exgcd(b,a%b,d,x,y);
int tmp=x;x=y;y=tmp-(a/b)*y;
}
}
求解不定方程ax+by=c的所有整数解。
。那么
即:
所以的一个剩余类,所以该补丁方程的通解为:
当
void Exgcd(ll a,ll b,ll &d,ll &x,ll &y){
// ax+by=gcd(a,b) : (x,y)
ll t=0;
if(b==0) d=a,x=1,y=0;
else{
Exgcd(b,a%b,d,x,y);
t=x;x=y;y=t-(a/b)*y;
}
}
int a,b,c;
int main(){
a=read();b=read();c=read();
int g=__gcd(a,b),a1=a/g,b1=b/g,c1=c/g,x1,y1,d;
Exgcd(a1,b1,d,x1,y1);
cout<<x1*c1<<" "<<c1*y1<<endl;
for(int i=-10000;i<=10000;i++){
int x=x1+b1*i,y=y1-a1*i;
cout<<x<<" "<<y<<"\n";
}
}