미완
{{{~cpp 
#include <iostream.h>   
#include <math.h>  

#define max( m, n ) ( m > n ? m : n )  
#define min( m, n ) ( m < n ? m : n )  
// Eclid Algorithm  
long gcd( long m, long n )  
{  
	long big = max( m, n );  
	long small = min( m, n );  
	long remain;  
	while( true )  
	{  
		remain = big % small;  
		if ( remain == 0 )  
			return small;  
		big = small;  
		small = remain;  
	}  
}  

void main()   
{   
/*      cout << gcd( 10, 5 ) << endl  
<< gcd( 11, 7 ) << endl  
<< gcd( 12, 8 ) << endl  
<< gcd( 13, 13) << endl 
<< gcd( 11111111, 12938 ) << endl; 
	*/          
	long A, B; 
	cin >> A >> B;  
	long a = A / gcd(A,B);   
	long b = B / gcd(A,B);  
	long xResult = max(A,B), yResult = max(A,B);  
	long range = max(a,b);
	double y;
	for ( long x = -range ; x <= range ; x++ ){
		y = 1/b - (a/b)*x;
		if ( int(y) == y )
			if ( abs(xResult) + abs(yResult) > abs(x) + abs(int(y)) ){  
				xResult = x;  
				yResult = int(y);  
			}  
	}
	cout << xResult << " " << yResult << " " << gcd(A,B) << endl; 
} 
}}}
----
[EuclidProblem]