C언어 226제] 유크리드 문제(Euclid Problem)

출처 : 반크_반크 20년 백서

 

문제]

유클리드가 밝혀낸 바에 따르면 임의의 정수 A, B에 대해 A와 B의 최대공약수를 D라고 할 때 AX+BY=D를 만족하는 정수 X와 Y가 존재한다. A와 B가 주어졌을 때 위 식으 만족시키는 X와 Y, 그리고 A와 B의 최대공약수 D를 구하라.

입력
한 줄에 두 개씩의 수가 입력되며 두 수는 각각 A와 B다. A와 B는 스페이스로 구분된다(A, B<1,000,000,001).

출력
입력된 각 줄에 대해 각각 스페이스로 구분된 세 개의 정수 X와  Y 그리고 D를 출력한다. 식을 만족하는 X와 Y가 여러 개 있으면, |X| + |Y|가 최소가 되는 값을 출력한다(X<=Y).

입력 예
4 6
17 17

출력 예
-1 1 2
0 1 17


출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제 51 유클리드 문제(Euclid Problem) p196

 

참고풀이]

#include <stdio.h>
#include <stdlib.h>

static int a, b, x, y, d;
static int r[100], k[100], xy[100][2];
static int check;

void Euclid()
{
   int i;
   int x1, y1, dx, dy;

   //유클리드 알고리즘을 이용해서 최대공약수와 x, y의 해를 구한다.
   if(a<b) { r[0]=b; r[1]=a; }
   else { r[0]=b; r[1]=a; }

   xy[0][0]=1;
   xy[0][1]=0;
   xy[1][0]=0;
   xy[1][1]=1;

   for(i=0; r[i+1] != 0; i++)
   {
      k[i] = r[i]/r[i+1];
      r[i+2] = r[i]%r[i+1];

      xy[i+2][0] = xy[i][0] - k[i]*xy[i+1][0];
      xy[i+2][1] = xy[i][1] - k[i]*xy[i+1][1];
   }

   d = r[i];
   if(a<b)
   {
      x = x1 = xy[i][1];
      y = y1 = xy[i][0];
   }
   else
   {
      x = x1 = xy[i][0];
      y = y1 = xy[i][1];
   }
   dx = b/d;
   dy = -a/d;

   //초기해에서 인접한 두 해를 비교해서 만족하는 해가 발견되면 바꾼다.
   if((abs(x)-abs(x1+dx)) + (abs(y) - abs(y1+dy))>0 || 
      (abs(x)+abs(y) == abs(x1+dx) + abs(y1+dy) && x1+dx <= y1+dy))
   {
      x=x1+dx;
      y=y1+dy;
   }
   else if((abs(x)-abs(x1-dx)) + (abs(y) - abs(y1-dy))>0 || 
      (abs(x)+abs(y) == abs(x1-dx) + abs(y1-dy) && x1-dx <= y1-dy))
   {
      x=x1-dx;
      y=y1-dy;
   }
}

int main()
{
   while(scanf("%d%d",&a,&b) != EOF)
   {
      if(a<1000000001 && b<1000000001)
      {
         Euclid();
         printf("%d %d %d\n",x, y, d);
      }
      else
         break;
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 가을