一步之遙【擴充歐幾裡得】

從昏迷中醒來，小明發現自己被關在X星球的廢礦車裡。

礦車停在平直的廢棄的軌道上。

他的面前是兩個按鈕，分别寫着“F”和“B”。

小明突然記起來，這兩個按鈕可以控制礦車在軌道上前進和後退。

按F，會前進97米。按B會後退127米。

透過昏暗的燈光，小明看到自己前方1米遠正好有個監控探頭。

他必須設法使得礦車正好停在攝像頭的下方，才有機會争取同伴的援助。

或許，通過多次操作F和B可以辦到。

礦車上的動力已經不太足，黃色的警示燈在默默閃爍...

每次進行 F 或 B 操作都會消耗一定的能量。

小明飛快地計算，至少要多少次操作，才能把礦車準确地停在前方1米遠的地方。

請填寫為了達成目标，最少需要操作的次數。

/*
  解不定方程
  97x + 127y = 1
  
  歐幾裡得定理 ---- 輾轉相除法  gcd
  擴充歐幾裡得定理
  Ax + By = gcd(A,B)
  理論基礎： gcd(A,B) == gcd(B,A%B)
  
  求出特解後，通解很好表示
  
  Ax + By = gcd(A, B)
  Ax + By = gcd(B, A%B)
  B * (A / B * x + y) + (A % B) * x = gcd(B, A%B)
  對比：
  A / B * x + y = 新x
  x = 新y
*/

public class Main {
    // 傳回最大公約數
    // xy: 順便解出的xy
    static int e_gcd(int A, int B, int[] xy) {
        if (B == 0) {
            xy[0] = 1;
            xy[1] = 0;
            return A;
        }

        int ans = e_gcd(B, A % B, xy);
        int t = xy[0];
        xy[0] = xy[1];
        xy[1] = t - A / B * xy[0];
        return ans;
    }

    public static void main(String[] args) {
        int[] xy = new int[2];
        int a = e_gcd(97, 127, xy);

        System.out.println(a);
        System.out.println(xy[0] + " " + xy[1]);
    }
}