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

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，然后求和中的最小值，就大功告成

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

Can I solve this problem with Dynamic Programming?

java

dynamic-programming

greatest-common-divisor

lcm