看了許久書(shū)終于從似懂非懂走了出來(lái)

設(shè)ax+by=gcd(a,b),解出符合條件的x,y;
當(dāng)b=0時(shí)，很顯然有一組必然解，x=1，y=0，即1a+00=gcd(a,b)=a;
即我們討論b!=0的情況；

ax+by=gcd(a,b)=gcd(b,a%b);

令一組解x1,y1使得x1b+y1(a%b)=gcd(b,a%b) =gcd(a,b) = ax+by;
a/b=k…r,k=a/b下取整，所以a%b=a-(a/b向下取整b);

所以x1b+y1( a-(a/b向下取整b) ) 化簡(jiǎn)得
y1*a+b(x1-y1(a/b向下取整)）
所以x=y1,y=x1-y1(a/b向下取整)

x1,y1,在下層已經(jīng)求得，從而遞推出x，y，最下面一層的解為x=1,y=0;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
exgcd(int a,int b,int &d,int &x,int &y){
    if(!b){x=1,y=0;d=a};
    else{
        exgcd(b,a%b,d,x,y);
        int t=x; x=y; y=t-y*(a/b);
    }
}