我可以用动态规划来解决这个问题吗？

Question

我如何在所有对 a 和 b 中找到具有“最小公倍数”LCM(a,b) = 498960 和“最大公约数”GDM(a, b ) = 12 一对具有最小总和a + b？

我用 O(n^2) 时间解决了这个问题：

public class FindLcmAndGcdClass {
    private int findGcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return findGcd(b, a % b);
    }

    private int findLcm(int a, int b, int gcd) {
        return (a * b) / gcd;
    }

    private void run() {
        int minSum = Integer.MAX_VALUE;
        int foundNumberOne = 0;
        int foundNumberTwo = 0;
        for (int i = 12; i <= 498960; i += 12) {
            for (int j = i; j <= 498960; j += 12) {
                int gcd;
                if (i < j) {
                    gcd = findGcd(j, i);
                } else {
                    gcd = findGcd(i, j);
                }
                int lcm = findLcm(i, j, gcd);

                if (gcd == 12 && lcm == 498960 && i + j < minSum) {
                    minSum = i + j;
                    foundNumberOne = i;
                    foundNumberTwo = j;
                }
            }
        }
        System.out.println(minSum);
        System.out.println(foundNumberOne);
        System.out.println(foundNumberTwo);
    }


    public static void main(String[] args) {
        var o = new FindLcmAndGcdClass();
        o.run();
    }
}

而且执行速度非常慢！我想这个问题可以用动态规划来解决。任何人都可以帮助提供更快速的解决方案吗？

Answer 1

我不确定这个问题是否可以用动态规划来解决，但我想到了一个时间复杂度O(sqrt(LCM * GCD))的解决方案。

众所周知，对于任意两个整数 a 和 b，LCM(a, b) * GCD(a, b) = a * b。因此，你可以先计算gcd和lcm的乘积（本题为5987520）。然后对于 sqrt(LCM * GCD) 下的所有因子，令 a 为因子之一，则 b = LCM * GCD / a 。测试 gcd(a, b) 是否 = 所需的 gcd，如果是，则计算和 a + b，然后找到和中的最小值，就完成了。