Как найти среди всех пар 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();
}
}
И это выполняется довольно медленно! Я думаю, что проблема может быть решена с помощью динамического программирования. Может ли кто-нибудь помочь с более быстрым решением?
@Stef Я имею в виду среди всех пар a, b с LCM (a, b) = 498960 и GDM (a, b) = 12, мне нужно найти пару с минимальной суммой a + b
Я не уверен, что этот вопрос можно решить с помощью динамического программирования, но я думаю о решении с временной сложностью 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?
Я имел в виду все факторы LCM*GCD. Я использовал sqrt, потому что для каждой правильной пары (a, b), (b, a) также есть правильная пара. Следовательно, вы можете просто зациклиться на sqrt, тогда для правильной пары (a, b) вы можете посчитать это дважды.