#UVa：10104－Euclid Problem

利用輾轉相除法的特性即可得解。

如果\(A \mod B = 0\)，則\(X = 0, Y = 1\)；反之則反。

如果\(A \mod B \neq 0, A \ge B\)，則根據遞迴式得知\(\gcd(A,B) = \gcd(A – B * \lfloor\frac{A}{B}\rfloor, B)\)，由此式可得\(\gcd(A – B * \lfloor\frac{A}{B}\rfloor, B) = (A – B * \lfloor\frac{A}{B}\rfloor) \times X’ + B \times Y’ = \gcd(A,B) = AX + BY\)，整理整理可得：\(AX’ – (B * \lfloor\frac{A}{B}\rfloor)X’ + BY’ = AX’ + B(Y’ – \lfloor\frac{A}{B}\rfloor X’) = AX + BY\)，所以兩相對照之下可得\(X = X’, Y = (Y’ – \lfloor\frac{A}{B}\rfloor X’)\)；反之則利用相同方式推導。

C++(0.060)

/*******************************************************/
/* UVa 10104 Euclid Problem                            */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2016/04/24                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int A, int B, int &X, int &Y){
  if( A % B == 0 ){
    X = 0;
    Y = 1;
    return B;
  }

  if( B % A == 0 ){
    X = 1;
    Y = 0;
    return A;
  }

  if( A >= B ){
    int x, y;
    int value = gcd(A + B * (-A/B), B, x, y);
    X = x;
    Y = y + x * (-A/B);
    return value;
  }
  else {
    int x, y;
    int value = gcd(A, B + A * (-B/A), x, y);
    X = x + (-B/A) * y;
    Y = y;
    return value;
  }
}


int main(){
  int A, B;
  while( scanf("%d%d", &A, &B) != EOF ){
    int X, Y;
    int value = gcd(A, B, X, Y);
    printf("%d %d %d\n", X, Y, value);
  }

  return 0;
}