imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:14Z

New page

미완
#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]]

EuclidProblem/Leonardong - Revision history

imported>Unknown at 05:23, 7 February 2021