Блог

Учитывая, что первое число, на которое нужно разделить все (1,2, .., 10), равно 2520. И учитывая, что первое число для деления всех (1,2, .., 20) равно 232792560. Найдите первое число, на которое нужно разделить все (1,2,..,100). (все последовательные числа от 1 до 100). Ответ должен быть получен менее чем за минуту.

Я пишу решение на Java, и я сталкиваюсь с двумя проблемами:

1. Как я могу вычислить, является ли само решение таким огромным числом, которое невозможно обработать? Я попытался использовать «BigInteger», я делаю много дополнений и делений, и я не знаю, увеличивает ли это мою временную сложность.
2. Как я могу вычислить это менее чем за минуту? Решение, о котором я думал до сих пор, даже не остановилось.

Это мой Java-код (с использованием больших целых чисел):

 public static boolean solved(int start, int end, BigInteger answer) {
    for (int i=start; i<=end; i  ) {
        if (answer.mod(new BigInteger(valueOf(i))).compareTo(new BigInteger(valueOf(0)))==0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    BigInteger answer = new BigInteger("232792560");
    BigInteger y = new BigInteger("232792560");
    while(!solved(21,100, answer)) {
        answer = answer.add(y);
    }
    System.out.println(answer);
}
 

Я пользуюсь тем фактом, что я уже знаю решение для (1, ..,20).

В настоящее время просто не останавливается.

Я думал, что мог бы улучшить его, изменив функцию solved , чтобы проверять только те значения, которые нас интересуют.

 For example:
100 = 25,50,100
99  = 33,99
98 = 49,98
97 = 97
96 = 24,32,48,96
 

И так далее. Но это простое вычисление для определения наименьшей группы необходимых чисел само по себе стало проблемой, для которой я не искал / не нашел решения. Конечно, временная сложность должна оставаться меньше минуты в любом случае.

Есть еще идеи?

Первое число, которое можно разделить на все элементы некоторого набора (что у вас там есть, несмотря на несколько иную формулировку), также известно как наименьшее общее кратное этого набора. LCM(a, b, c) = LCM(LCM(a, b), c) и так далее, так что в общем случае его можно вычислить, взяв n — 1 попарных LCMS, где n — количество элементов в наборе. BigInteger не имеет lcm функции, но LCM может быть вычислен с помощью a * b / gcd(a, b) so в Java с BigInteger :

 static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}
 

Для 1-20 вычисление LCM таким образом действительно приводит к 232792560. Это легко сделать и до 100.

Найдите все max prime powers в вашем ассортименте и возьмите их продукт.

Например,. 1-10: 2^3, 3^2, 5^1, 7^1: продукт равен 2520, что является правильным ответом (а не 5250). Вы можете найти простые числа через сито Эратосфена или просто загрузить их из списка простых чисел.

Поскольку 100 мало, вы можете решить это, произведя разложение на простые множители всех чисел от 2 до 100 и сохранив наибольший показатель каждого простого числа среди всех факторизаций. На самом деле, попытки деления на 2, 3, 5 и 7 будет достаточно, чтобы проверить простоту до 100, и есть только 25 простых чисел для рассмотрения. Вы можете реализовать простое сито для поиска простых чисел и выполнения факторизации.

После того, как вы нашли все показатели простого разложения lcm, вы можете либо оставить это в качестве ответа, либо выполнить умножения явно.