java - 要根据输入数字本身评估的两个数字的 GCD/LCM

Question

考虑给我们的输入为 a=21, b=36 并且 GCD (a,b) 为 d=3。

如果我们应该通过求解方程a * x + b * y = d 来实现 GCD。我们如何计算此等式中 x 和 y 的正负 整数的众多组合，以获取满足此等式的结果。

Eg: a=21, b=36, (GCD) d=3
21 * x + 36 * y = 3
x = ? and y = ?
Sample answer: x=-5,y=3

如何在 JAVA 中实现？

Answer 1

你可以通过 Extended Euclidean algorithm 来完成.实现在这里

public class ExtendedEuclid {

   //  return array [d, a, b] such that d = gcd(p, q), ap + bq = d
   static int[] gcd(int p, int q) {
      if (q == 0)
         return new int[] { p, 1, 0 };

      int[] vals = gcd(q, p % q);
      int d = vals[0];
      int a = vals[2];
      int b = vals[1] - (p / q) * vals[2];
      return new int[] { d, a, b };
   }

   public static void main(String[] args) {
      int p = Integer.parseInt(args[0]);
      int q = Integer.parseInt(args[1]);
      int vals[] = gcd(p, q);
      System.out.println("gcd(" + p + ", " + q + ") = " + vals[0]);
      System.out.println(vals[1] + "(" + p + ") + " + vals[2] + "(" + q + ") = " + vals[0]);
   }
}

输入:int vals[] = gcd(21, 36);

输出:

gcd(21,36) = 3
-5(21) + 3(36) = 3