考虑给我们的输入为a=21, b=36和GCD (a,b) is d=3。
如果我们应该通过求解方程a * x + b * y = d来实现GCD 。我们如何在该方程式中评估positive and negative整数的众多组合，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？
您可以通过扩展欧几里得算法来做到这一点。实现在这里
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
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句