扩展欧几里得算法

/* 
扩展欧几里得算法
给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)
设aX' + bY' = gcd(a, b)
  bX'' + (a mod b)Y'' = gcd(b, a mod b)
  
  bX'' + (a mod b)Y'' = gcd(a, b)
  bX'' + (a mod b)Y'' = aX' + bY' 
  bX'' + [a - b * (a / b)]Y'' = aX' + bY' 
  bX'' + aY'' - b * (a / b)Y'' = aX' + bY'
  aY'' + b[X'' - Y'' * (a / b)] = aX' + b Y'
  X' = Y''
  Y' = X'' -Y'' * (a / b)
*/
public class Main {
    public static void main(String[] args) {
        System.out.println();
    }

    static int x, y;

    static int extgcd(int a, int b) {
        int d = a;
        if (b == 0) {
            x = 1;
            y = 0;
        } else {
            d = extgcd(b, a % b);
            int t = x;
            x = y;
            y = t - y * (a / b);
        }
        return d;
    }

}