Can I solve this problem with Dynamic Programming?

Question

How I find among all pairs a and b with a "least common multiple" LCM(a,b) = 498960 and a "greatest common divisor" GDM(a, b) = 12 a pair with minimum sum a + b?

I solved this with O(n^2) time:

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();
    }
}

And it executes quite slowly! I guess the problem can be solved with Dynamic Programming. Can anyone help with more fast solution?

Answer 1

I am not sure if this question can be solved with dynamic programming, but I think of a solution with time complexity O(sqrt(LCM * GCD)).

It is well known that for any two integers a and b, LCM(a, b) * GCD(a, b) = a * b. Therefore, you can first calculate the product of the gcd and lcm, (which is 5987520 in this question). Then for all its factors under sqrt(LCM * GCD), let a be one of the factors, then b = LCM * GCD / a. Test if gcd(a, b) = the required gcd, if so calculate the sum a + b, then find the minimum among the sums, and you are done.