너무 어려워서 다음 사이트를 참고하였습니다:

• 유클리드 호제법

파이썬입니다

def euclid(a, b, result=[]):
    m, n = divmod(a,b)
    if n != 0:
        result.append((1,-m))
        return euclid(b, n, result)
    else:
        result.reverse()
        if result:
            x,y = result[0]
            for c in result[1:]:
                x, y = y*c[0], x+y*c[1]
        else:
            x, y = 0, 1
        return x, y, b


print euclid(1071, 1029, [])
print euclid(1029, 1071, [])
print euclid(19332, 78696, [])
print euclid(333, 222, [])
print euclid(333, 333, [])
print euclid(333, 332, [])

파이썬이고, 흔히 알려진 유클리드 알고리즘을 이용했습니다. 코딩이 서툴러서 더 줄일 수 있을것 같은데 잘 못하겠네요.

유클리드 호제법

자연수 A > B가 있을때 다음과 같은 방법으로 최대공약수를 구할 수 있다.

A = Bq_1 + r_1, B = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, ... 를 반복한다.

r_i는 점점 줄어들기 때문에 어느 순간 0이 되는데 r_n = 0이라면 r_{n-1}이 바로 최대공약수다.

그리고 위 방법을 조금만 변형하면 임시로 X,Y를 찾을수 있고 적절히 조절해서 문제에서 요구하는 조건을 맞출 수 있습니다.

#
# http://codingdojo.kr/scode/437
#

#
# Finding Linear Combination for Greatest Common Divisor
#
def Euclidean_algorithm(num1, num2):

    # Begin finding quotients and greatest common divisor
    quotient = []
    remainder = [num1, num2]
    while True:
        if remainder[-1] == 0:
            quotient.pop()
            remainder.pop()
            break
        else :
            quotient.append(divmod(remainder[-2],remainder[-1])[0])
            remainder.append(divmod(remainder[-2],remainder[-1])[1])

    gcd = remainder[-1]
    lcm = num1 * num2 / gcd

    # Begin finding a linear combination
    lin_num1 = [1,0]
    lin_num2 = [0,1]

    for quot in quotient:
        lin_num1.append(lin_num1[-2] - quot * lin_num1[-1])
        lin_num2.append(lin_num2[-2] - quot * lin_num2[-1])

    temp_x = lin_num1[-1]
    temp_y = lin_num2[-1]
    to_min = divmod(temp_x, num2/gcd)[0]

    temp = [ [temp_x - to_min*num2/gcd, temp_y  + to_min*num1/gcd],
             [temp_x - (to_min + 1)*num2/gcd, temp_y + (to_min + 1)*num1/gcd] ]

    if abs(temp[0][0]) + abs(temp[0][1]) < abs(temp[1][0]) + abs(temp[1][1]):
        return [gcd, temp[0][0], temp[0][1]]
    elif abs(temp[0][0]) + abs(temp[0][1]) > abs(temp[1][0]) + abs(temp[1][1]):
        return [gcd, temp[1][0], temp[1][1]]
    elif temp[0][0] <= temp[0][1]:
        return [gcd, temp[0][0], temp[0][1]]
    else :
        return [gcd, temp[1][0], temp[1][1]]

#
# Main Part
#

while True:
        input = input("Input two positive integers separated by space : ")
        a, b = input.split()
        A, B = int(a), int(b)
        if str(A) != a or str(B) != b or A > 10E9 or B > 10E9:
            print("The input is incorrect")
        else :
            break

result = Euclidean_algorithm(max(A,B), min(A,B))

if A == max(A,B) :
    X, Y = int(result[1]), int(result[2])
else :
    Y, X = int(result[1]), int(result[2])

print(X, Y, result[0])

풀긴 했는데 제약 조건이 있습니다.

X, Y값의 범위가 ~1000~1000사이에서만 체크됩니다.

그냥 학부생 수준이라 생각하고 참고만 하세요~

#!/usr/bin/env python

# gcd(greatest common divisor)
def get_gcd(A, B):
    while B != 0:
        r = A%B
        (A,B) = (B,r)
    return A

def get_xy(A, B, D):
    min = -1000
    max = 1000
    sum_xy = 99999999
    for i in range(min,max):
        for j in range(min,max):
            if i>j: # Check1: x <= y
                continue
            if (A*i+B*j) == D:
                temp_sum = abs(i)+abs(j)
                if temp_sum < sum_xy: # Check2: minimum |x|+|y|
                    sum_xy = temp_sum
                else:
                    continue
                (x,y) = (i,j)
    return "%d %d " % (x, y)

def main():
    (N1, N2) = (400, 250)
    D = get_gcd(N1, N2)
    print "Input: %d %d" % (N1, N2)
    print "Output: "+get_xy(N1, N2, D)+str(D)

if __name__ == "__main__":
    main()

파이썬입니다.

def GCM(a,b):
    c = min(a,b)
    while True:
        if (a%c == 0 and b%c == 0):
            return c
        else:
            c-=1

def Euclid(a, b):
    D=GCM(a,b)
    y=0.0
    z=0.0
    while True:
        x=D/a - b*y/a
        w=D/a - b*z/a

        if (x%1==0):
            return (min(x,y), max(x,y), D)
        if (w%1==0):
            return (min(w,y), max(w,y), D)

        y+=1.0
        z-=1.0

print Euclid(4.0, 6.0)

C#으로 작성했습니다. 부끄럽게도 euclid algorithm은 처음 접해 보는 거라 이곳을 참조하게 되었습니다. http://www.trans4mind.com/personal_development/mathematics/numberTheory/euclidsAlgorithmAndExtendedAlgorith.htm 제 코드는 엄밀히 말해서 항상 X <= Y인 값을 출력하지 않습니다. 예를 들어, A = 7, B = 17이 입력되었을 경우, X가 Y보다 큽니다. 일단 푼 데까지만 올리고 다음에 다시 찾아뵙겠습니다.

        public class Euclid
        {
            public int X1 { get; set; }
            public int X2 { get; set; }
            public int Y1 { get; set; }
            public int Y2 { get; set; }
            public int R1 { get; set; }
            public int R2 { get; set; }
            public int Q { get; set; }
            public Euclid(int a, int b)
            {
                X1 = 1;
                X2 = 0;
                Y1 = 0;
                Y2 = 1;
                R1 = b;
                R2 = a%b;
                Q = a/b;
            }
            public void UpdateXs(int x1, int x2)
            {
                X1 = x1;
                X2 = x2;
            }
            public void UpdateYs(int y1, int y2)
            {
                Y1 = y1;
                Y2 = y2;
            }
            public void UpdateRs(int r1, int r2)
            {
                R1 = r1;
                R2 = r2;
            }
        }

        public void FindEuclid(Euclid e)
        {
            if (e.R2 == 0) return;
            var x = e.X1 - e.X2*e.Q;
            var y = e.Y1 - e.Y2*e.Q;
            e.UpdateXs(e.X2, x);
            e.UpdateYs(e.Y2, y);
            var remainder = e.R1%e.R2;
            if (remainder == 0) return;
            e.Q = e.R1/e.R2;
            e.UpdateRs(e.R2, remainder);
            FindEuclid(e);
        }

Ruby

참고 알고리즘 : Extended Euclidean, Bézout's identity

bz =->x,y { a,s,b,t = 1,0,0,1
           (x,q,y=y,*x.divmod(y); a,s,b,t=s,a-q*s,t,b-q*t) until y.zero?; [a,b,x] }

Test

# p bz[1071,1029] #=> [-24,25,21]
expect(bz[4,6]).to eq [-1,1,2]
expect(bz[17,17]).to eq [0,1,17]
expect(bz[1071,1029]).to eq [-24,25,21]
expect(bz[78696,19332]).to eq [212,-863,36]

확장 유클리드 알고리듬을 적용하였고, 두 수를 나눈 나머지를 통해서 다음 단계로 넘어가므로 재귀호출을 해도 단계가 많지 않을거라 생각되어 재귀로 짰습니다.

def do(a, b):
    q, r = divmod(a, b)
    if r == 0:
        return 0, 1, b
    x, y, g = do(b, r)
    return y, x - q * y, g

data = []
while True:
    s = input()
    if not s:
        break
    data.append([int(x) for x in s.split()[:2]])

for d in data:
    print(do(*d))

def eu(a, b, n = [], depth = 0):
    if depth == 0:
        n = []
    if a < b:
        a, b = b, a
    if a%b == 0:
        return b, n
    n.append(a//b)
    return eu(b, a%b, n, depth + 1)

def s(n):
    i = len(n)
    if i <= 0: return complex(0, 1)
    elif i == 1: return complex(1, -n[1-1])
    elif i == 2: return complex(0, 1) - n[2-1]*complex(1, -n[1-1])
    return s(n[:-2]) - n[-1]*s(n[:-1])

while __name__ == '__main__':
    inpt = list(map(int, input(">>>").split()))
    r_1 = eu(*inpt); r_2 = s(r_1[1]); r_2 = [r_2.real, r_2.imag];
    if inpt[0] < inpt[1]: r_2.reverse()
    print(r_1[0], *r_2)

하얗게 불태웠습니다... 파이썬 3.5.1

ax+by = gcd(a,b) 의 정수해 (x,y)를 찾기 위해서 bx'+(a%b)y' = gcd(a,b) 를 성립하는 x',y'이 존재한다고 가정합니다.

a%b = a - (a/b)*b이므로 이것을 대입하면 ay' + b(x'-(a/b)y' = gcd(a,b) 입니다. 그리고 b = 0이면 gcd(a,b) = a입니다.

#include <iostream> 
#include <cstdlib> 
#include <cstdio> 
#include <algorithm> 
using namespace std;  

int extgcd(int a,int b,int &x,int &y){
    int d = a; 
    if (b != 0){
        d = extgcd(b,a%b,y,x);

        y -= (a/b)*x; 
    }else{
        x = 1; y = 0;

    }
    return d;

}
int main(){
    int n,m; 
    while (~scanf("%d %d",&n,&m)){
        int x,y; 
        int gcd = extgcd(n,m,x,y);

        // x,y,d를 출력한다. 
        printf("%d %d %d\n",x,y,gcd);

    }
    return 0; 
}

Delpi 2010

procedure fnEuclidProblem(a, b: Integer; var X, Y, d: Integer);
  function gcd(P, Q: Integer): Integer;
  begin
    if Q = 0 then
      exit(P);
    result := gcd(Q, P mod Q);
  end;

var
  a1, B1, i, j, n1, n2, x1, y1, nMax: Integer;
  bOk: boolean;
begin
  d := gcd(a, b);
  a1 := a div d;
  B1 := b div d;

  X := 0;
  Y := 0;
  nMax := 10000;
  for i := -a1 to a1 do
  begin
    // 최소값 이므로 
    bOk := False;
    n1 := B1 * i;
    // A1*X+B1*Y=1 
    for j := -B1 to i do //X <= Y 인 값
    begin
      if a1 * j + n1 = 1 then
      begin
        n2 := abs(i) + abs(j);
        if nMax > n2 then
        begin
          nMax := n2;
          X := j;
          Y := i;
        end;
      end;
    end;
  end;

end;

procedure TForm4.btnEuclidProblemClick(Sender: TObject);
var
  X, Y, d: Integer;
begin
  fnEuclidProblem(4, 6, X, Y, d);
  Memo1.Lines.Add(format('AX + BY = D => (%d, %d) : x:%d, y:%d, 최대공약수: %d', [4, 6, X, Y, d]));
  fnEuclidProblem(17, 17, X, Y, d);
  Memo1.Lines.Add(format('AX + BY = D => (%d, %d) : x:%d, y:%d, 최대공약수: %d', [17, 17, X, Y, d]));

end;

자바입니다

package study;

import java.util.Scanner;

public class euclid {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        solve(A,B);
    }

    public static void solve(int A, int B){
        int X=0, Y=0, D=0;
        int min;
        min = Math.min(Math.abs(A), Math.abs(B));

        for (int i = 1; i < min + 1; i++) {
            if (A % i == 0 && B % i == 0 && D < i) {
                D = i;
            }
        }

        for (int n = 0; A * X + B * Y != D; n++) {
            for (int j = 0; j <= n; j++) {
                int i=n-j;
                if (A * i + B * j == D) {
                    X = Math.min(i, j);
                    Y = Math.max(i, j);
                    break;
                } else if (0 - A * i + B * j == D) {
                    X = Math.min(0-i, j);
                    Y = Math.max(0-i, j);
                    break;
                } else if (A * i - B * j == D) {
                    X = Math.min(i, 0-j);
                    Y = Math.max(i, 0-j);
                    break;
                }
            }
        }
        System.out.println(X+" "+Y+" "+D);
    }
}

유클리드 호제법같은건 모르고 그냥 일일히 돌렸는데

숫자가 조금 커지니까 오버플로 문제인지 맛이 가네요...

import java.util.Scanner;
import java.util.StringTokenizer;

public class euclidproblem {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);

        while(true) {
            String input = scan.nextLine();
            StringTokenizer st = new StringTokenizer(input, " ");
            String token = null;

            token = st.nextToken();
            int A = Integer.parseInt(token);

            token = st.nextToken();
            int B = Integer.parseInt(token);

            getXY(A, B, gcd(A, B));
        }
    }
    static void getXY(int A, int B, int gcd) {

        boolean go = true;
        int start = -1, end = 1;
        while(go) {
            for(int x = start ; x< end; x++) {
                for(int y = start; y< end; y++) {
                    if(A*x + B*y == gcd && x <= y) {
                        System.out.println(x + " " + y +" " +gcd);
                        go = false;
                    }
                }
            }
            end++;
            start--;
        }
    }
    static int gcd(int A, int B) {
        int r = 1;
        int high, low;
        if(A > B) {
            high = A;
            low = B;
        } else {
            high = B;
            low = A;
        }

        while(r!=0) {
            r = high % low;
            high = low;
            low = r; 

        }
        return high;
    }
}

import java.util.Scanner;

public class EuclidProblem {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        solve(sc.nextInt(), sc.nextInt());
    }

    private static void solve(int n, int m) {
        int a, b;

        if (n > m) {
            a = m;
            b = n;
        } else {
            a = n;
            b = m;
        }

        int c = gcd(b, a);
        int y = 0;
        while (true) {
            if ((1 - (b / c) * y) % (a / c) == 0) {
                System.out.println(((c - (y * b)) / a) + " " + y + " " + c);
                break;
            }
            y++;
        }
    }

    private static int gcd(int a, int b) {
        int c = a > b ? a % b : b % a;
        return c == 0 ? b : gcd(b, c);
    }
}

object EuclidProblem
{
  def SDrs(N : Int): IndexedSeq[Int] = (1 to N / 2) filter(x => N % x == 0)
  def gcd(N1SD: IndexedSeq[Int], N2SD: IndexedSeq[Int], i: Int, j: Int): Int =
    if(N1SD(i) == N2SD(j)) N1SD(i)
    else if(j > 0) gcd(N1SD, N2SD, i, j - 1)
    else if(j == 0) gcd(N1SD, N2SD, i - 1, N2SD.length - 1)
    else 0
  def SEu(N1: Int, N2: Int, gcd : Int, X: Int, Y: Int, SEuL: List[Int]): List[Int] =
    if(N1 * X + N2 * Y == gcd) SEu(N1, N2, gcd, X, Y + 1,SEuL.:+(X).:+(Y))
    else if(Y < 1000) SEu(N1, N2, gcd, X, Y + 1,SEuL)
    else if(X < 1000) SEu(N1, N2, gcd, X + 1, -1000,SEuL)
    else SEuL
  def main(args: Array[String]): Unit ={
    val GCD1 = gcd(SDrs(12),SDrs(15),SDrs(12).length-1,SDrs(15).length - 1)
    val SEuL = List[Int]()
    val Result = SEu(12,15, GCD1, -1000, -1000, SEuL)
    print(Result)
  }
}

탐색 범위 내의 성립하는 X,Y쌍을 전부 출력하게 헀습니다. 유클리드 호제법은 사용하지 않았습니다.

import java.util.Scanner;

public class test {
    static long GCD(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return GCD(b, a % b);
        }
    }

    /*
     A = aD, B = bD
     aDX + bDY = D
     aX + bY = 1     
     */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A, B, D, a, b, X, Y;
        A = sc.nextLong();
        B = sc.nextLong();
        D = GCD(A, B);
        a = A / D;
        b = B / D;

        for (long y = 0; ; y++) {
            for (long x = 0; x <= y; x++) {             
                if (a * x + b * y == 1) { X = x; Y = y; }
                else if (a * x - b * y == 1) { X = x; Y = -y; }
                else if (b * y - a * x == 1) { X = -x; Y = y; }
                else if (a * x + b * y == -1) { X = -x; Y = -y; }
                else continue;

                if (X > Y) { long t = X; X = Y; Y = t; }
                System.out.printf("%d %d %d\n", X, Y, D);
                return;
            }
        }            

    }
}

|X| <= |Y| 로 풀었네요. X <= Y 로 하면 부호가 너무 복잡해져서;; X, Y를 양의 정수로 한정하면 훨씬 쉬울 것 같습니다.

import java.util.Scanner;

public class EuclidProblem {

    public static int gcd(int a, int b) {
        while (b != 0) {
          int temp = a % b;
          a = b;
          b = temp;
        }
        return Math.abs(a);
      }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);

        for(int i=0; i<2; i++){
            String[] numbers = sc.nextLine().split(" ");
            int a = Integer.parseInt(numbers[0]);
            int b = Integer.parseInt(numbers[1]);
            int result = gcd(a,b);
            int x = 0;
            int y = 0;

            int count = 0;
            while(true){
                if(result == a * x + b * y){
                    break;
                }else{
                    if(count % 3 == 0){
                        x--;
                    }else if(count % 3 == 1){
                        x++;
                        y++;
                    }else if(count % 3 == 2){
                        x--;
                    }
                    count++;
                }
            }
            System.out.println(x + " " + y + " " +result);
        }
        sc.close();

    }

}

import java.util.Scanner;

public class EuclidProblem {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] AB = sc.nextLine().split(" ");
        int A = Integer.valueOf(AB[0]), B = Integer.valueOf(AB[1]), Gcd = 0;
        for (int i = 1; i < (A > B ? A : B) + 1; i++)
            if (i <= A && A % i == 0 && i <= B && B % i == 0)
                Gcd = i;
        outerLoop: for (int i = 0; i < (A > B ? A : B) + 1; i++)
            for (int j = 0; j > (A > B ? B : A) * -1 - 1; j--)
                if (A * (A > B ? i : j) + B * (A > B ? j : i) == Gcd) {
                    System.out.println((A > B ? i : j) + " " + (A > B ? j : i) + " " + Gcd);
                    break outerLoop;
                }
    }
}

def gcd(a,b):
    while b != 0:
        a,b = b,a%b
    return a

while 1:
    a,b = map(int,input('a b: ').split())
    if not a: break
    D = gcd(a,b)
    y = lambda x: (D-a*x)/b
    id = 0
    while 1:
        if not y(id)%1: break
        id -= 1
    print(id,int(y(id)),D)

AX+BY=D, X<=Y 를 만족하는 정수해는 2사분면에 존재한다
따라서 X <= 0 인 범위에서 정수 조합을 찾는다