时间戳

首页 > 解决方案 > 最大互质除数

java - 最大互质除数

问题描述

给定两个正数 A 和 B。您需要找到最大值整数 X 使得： X 除以 A 即 A % X = 0 X 和 B 互质即 gcd(X, B) = 1 例如，A = 30 B = 12 我们返回 X = 5

在此代码中，cpFact 返回所需的输出。最好的情况是当 gcd(int A, int B)=1 时，会返回 A 的实际值。否则，while 循环迭代以获得所需的输出，每次通过将 A 的值除以 gcd(A, B) 来减小 A 的值。但是我没有明白为什么通过将 A 与 gcd(A, B) 相除来减少 A 的逻辑。谁能解释一下它背后的逻辑？

public class Solution 
{
    public static void main(String[] args) {
        System.out.println(cpFact(48,16));
    }
    public static int cpFact(int A, int B) 
    {
     while(gcd(A, B)!=1
     {
         A=A/gcd(A, B);
     }
        return A;
    }
    public static int gcd(int X,int B)
        {
            if(X == 0)
              return B;
            return gcd(B%X,X);
        }
}

标签： javalogic

解决方案

当您将 A 除以 A 和 B 的最大公分母时，您将获得一个新值 A1，它与 A 具有所有相同的分母，除了这个（见底部的解释）。

同时，A1 按定义划分 A。

然后您可以将 A 替换为 A1 并继续用 B 降序检查其其余公分母，直到只剩1下一个，这意味着 A 的最后检查值就是答案。

第一句话的解释：

想象A和B可以写成：

A = a * d * e
B = a * b * c * e * f
  where a > b > c > d > e > f

那么 的最大公分母 (GCD)(A,B)是a。这意味着，如果你除以A，a那么你得到A1 = A / a = d * e。

A可被A1（因为A / A1 = a）整除，您现在可以找到 的 GCD (A1,B)，这将是e的下一个公分母（(A,B)按降序排列）。

推荐阅读