Могу ли я решить эту проблему с помощью динамического программирования?

Как найти среди всех пар a и b с «наименьшим общим кратным» НОК(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();
    }
}

И это выполняется довольно медленно! Я думаю, что проблема может быть решена с помощью динамического программирования. Может ли кто-нибудь помочь с более быстрым решением?

«Как найти минимальное значение суммы a и b» Не могли бы вы пояснить, что вы подразумеваете под "минимальной суммой значений a и b"?
Stef 28.03.2022 12:54

@Stef Я имею в виду среди всех пар a, b с LCM (a, b) = 498960 и GDM (a, b) = 12, мне нужно найти пару с минимальной суммой a + b

Vyguzov Aleksandr 28.03.2022 13:00
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
2
74
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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, затем найдите минимум среди сумм, и все готово.

Не могли бы вы объяснить Then for all its factors under sqrt(LCM * GCD). Какие факторы? А почему sqrt, если a и b могут быть разными числами? Может, просто разделить числа от 12 до 498960?

Vyguzov Aleksandr 29.03.2022 06:12

Я имел в виду все факторы LCM*GCD. Я использовал sqrt, потому что для каждой правильной пары (a, b), (b, a) также есть правильная пара. Следовательно, вы можете просто зациклиться на sqrt, тогда для правильной пары (a, b) вы можете посчитать это дважды.

L3ungj 02.04.2022 06:16

Другие вопросы по теме