#include<fstream.h>
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int a,b,c,d,s,t,r;
int euclidextins(int a,int b,int &s,int &t){
int q,s1,s2,t1,t2;
if(b == 0){s = q; t = s; return a;}
s1 = 1; s2 = 0; t1 = 0; t2 = 1;
while((r)){
s = s1 - s2 * q; s1 = s2; s2 = s;
t = t1 - t2 * q; t1 = t2; t2 = t;
a = b; b = r; r = a % b; q = a / b;
}
}
int main(){
g<<"a=";f>>a;
g<<"b=";f>>b;
d = euclidextins(a,b,s,t);
g<<"("<<a<<","<<b<<") ="<<d<<"=("<<s<<"*"<<a<<"("<<t<<")"<<b<<'\n';
return 0;
}