#include<iostream> using namespace std; typedef struct node{ int x; int y; int q; }node; node t; node extend_euclid(int a,int b) { if(b==0) { t.x=1; t.y=0; t.q=a; return t; } else{ extend_euclid(b,a%b); int tmp=t.x; t.x=t.y; t.y=tmp-(a/b)*t.y; cout<<t.x<<":"<<t.y<<":"<<t.q<<endl; } return t; } int main() { int a,b; node t1; cin>>a>>b; t1=extend_euclid(a,b); //cout<<t1.x<<":"<<t1.y<<":"<<t1.q<<endl; return 0; }
http://baike.baidu.com/view/1478219.htm
http://www.cnblogs.com/ka200812/archive/2011/09/02/2164404.html