미완
~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; }