Найти сумму наименьших общих кратных всех подмножеств заданного множества

Задано: установлено A = {a₀, a₁, ..., a_N-1} (1 &leq; N &leq; 100), с 2 &leq; a_i &leq; 500.

Задано: Найти сумму всех наименее общих кратных (LCM) всех подмножеств A размером не менее 2.

LCM набора B = {b₀, b₁, ..., b_k-1} определяется как минимальное целое число B_min такое, что b_i | B_min для всех 0 &leq; i < k.

Пример:

Пусть N = 3 и A = {2, 6, 7}, тогда:

LCM({2, 6})      =    6
LCM({2, 7})      =   14
LCM({6, 7})      =   42
LCM({2, 6, 7})   =   42
----------------------- +
answer              104

Наивный подход состоял бы в том, чтобы просто вычислить LCM для всех подмножеств O(2^N), что невозможно для достаточно больших N.

Эскиз решения:

Задача получается из конкурса ^* который также предоставил эскиз решения . Именно здесь возникает моя проблема: я не понимаю намекающий подход.

Решение читает (по модулю некоторые небольшие проблемы с фиксированной грамматикой):

Решение немного сложно. Если мы внимательно наблюдаем, мы видим, что целые числа находятся между 2 и 500. Итак, если мы просто факторизуем числа, мы получаем следующие максимальные мощности:

Кроме этого, все простые числа имеют мощность 1. Таким образом, мы можем легко вычислить все возможные состояния, используя эти целые числа, оставляя состояния 9 * 6 * 4 * 4 * 3 * 3 * 3 * 3, что почти равно 70000. Для других целых чисел мы можем сделать dp следующим образом: dp[70000][i], где i может быть 0 до 100. Однако, поскольку dp[i] зависит от dp[i-1], поэтому dp[70000][2] достаточно. Это оставляет сложность n * 70000, которая возможна.

У меня есть следующие конкретные вопросы:

Что подразумевается под этими состояниями?
Поддерживает ли dp динамическое программирование, и если да, то какое рекуррентное отношение решается?
Как dp[i] вычисляется из dp[i-1]?
Почему большие простые числа не влияют на количество состояний? Каждое из них происходит либо 0, либо 1 раз. Если число состояний не будет умножено на 2 для каждого из этих простых чисел (что опять приведет к неосуществимому пространству состояний)?

_{^* Оригинальное описание проблемы можно найти из этого источника (проблема F). Этот вопрос является упрощенной версией этого описания.}

Ответ 1

Обсуждение

После прочтения фактического описания конкурса (стр. 10 или 11) и эскиз решения, я должен заключить, что автор эскиза решения довольно неточно в их написании.

Проблема высокого уровня заключается в вычислении ожидаемого срока службы, если компоненты выбраны случайным образом с помощью честной броски монет. Это то, что приводит к вычислению LCM всех подмножеств - все подмножества эффективно представляют пространство выборки. Вы можете получить любой возможный набор компонентов. Время отказа устройства основано на LCM набора. Таким образом, ожидаемое время жизни - это среднее значение LCM всех множеств.

Обратите внимание, что это должно включать LCM множеств только с одним элементом (в этом случае мы бы предположили, что LCM является самим элементом). Эскиз решения, похоже, саботирует, возможно, потому, что они обрабатывали его менее элегантно.

Что подразумевается под этими состояниями?

Автор эскиза дважды использует слово state, но, видимо, ему удается переключать значения. При первом использовании состояния слова, похоже, речь идет о возможном выборе компонентов. Во втором использовании они, вероятно, говорят о возможных временах сбоя. Они могут путать эту терминологию, потому что их динамическое программирующее решение инициализирует значения от одного использования слова, а отношение повторения связано с другим.

Поддерживает ли dp динамическое программирование?

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

Если да, то какое рекуррентное отношение решается? Как вычисляется dp [i] из dp [i-1]?

Все, что я могу думать, заключается в том, что в своем решении состояние i представляет время отказа, T(i), с количеством раз на этот раз до отказа, подсчитано dp[i]. Полученная сумма должна была бы суммировать все dp[i] * T(i).

dp[i][0] будет тогда временем сбоя, отсчитываемым только для первого компонента. dp[i][1] будет тогда временем сбоя, отсчитываемым для первого и второго компонентов. dp[i][2] будет для первого, второго и третьего. Etc..

Инициализировать dp[i][0] с помощью нулей, кроме dp[T(c)][0] (где c - первый рассмотренный компонент), который должен быть 1 (так как это время отказа компонента было подсчитано один раз до сих пор).

Чтобы заполнить dp[i][n] из dp[i][n-1] для каждого компонента c:

Для каждого i скопируйте dp[i][n-1] в dp[i][n].
Добавить 1 в dp[T(c)][n].
Для каждого i добавьте dp[i][n-1] в dp[LCM(T(i), T(c))][n].

Что это делает? Предположим, вы знали, что у вас есть время до отказа j, но вы добавили компонент со временем до отказа k. Независимо от того, какие компоненты у вас были раньше, ваше новое время неудачи - LCM(j, k). Это следует из того, что для двух множеств A и B, LCM(A union B} = LCM(LCM(A), LCM(B)).

Аналогичным образом, если мы рассмотрим время отказа T(i) и наше новое время компонента для отказа T(c), итоговое время отказа - LCM(T(i), T(c)). Обратите внимание, что мы записали это время к ошибке для конфигураций dp[i][n-1], поэтому мы должны записать, что много новых времен к ошибке после ввода нового компонента.

Почему большие простые числа не вносят вклад в число состояний?

Каждое из них происходит либо 0, либо 1 раз. Если число состояний не будет умножено на 2 для каждого из этих простых чисел (что опять приведет к неосуществимому пространству состояний)?

Вы правы, конечно. Однако в эскизе решения указано, что числа с большими штрихами обрабатываются другим (неуказанным) способом.

Что произойдет, если мы включим их? Количество состояний, которые нам нужно было бы представлять, взорвалось бы в нецелесообразном числе. Следовательно, автор учитывает такие цифры по-разному. Обратите внимание, что если число, меньшее или равное 500, включает в себя просто больше 19, другие коэффициенты умножаются на 21 или меньше. Это делает такие числа пригодными для принудительного форматирования, не требуя таблиц.

Ответ 2

Первая часть редакции кажется полезной, но вторая часть довольно расплывчата (и, возможно, бесполезна, я бы предпочел закончить этот ответ, чем понять это).

Предположим, что на данный момент вход состоит из попарно различных простых чисел, например, 2, 3, 5 и 7. Тогда ответ (для суммирования всех множеств, где LCM целых чисел 0 равен 1), составляет

(1 + 2) (1 + 3) (1 + 5) (1 + 7),

потому что LCM подмножества точно равна произведению здесь, поэтому просто умножьте его.

Ослабляем ограничение на то, что простые числа попарно различны. Если у нас есть вход как 2, 2, 3, 3, 3 и 5, то умножение выглядит как

(1 + (2^2 - 1) 2) (1 + (2^3 - 1) 3) (1 + (2^1 - 1) 5),

поскольку 2 появляется с кратностью 2, а 3 появляется с кратким 3, а 5 появляется с кратностью 1. Что касается, например, только набора из 3s, существуют 2^3 - 1 способы выбора подмножества, которое включает в себя 3, и 1 способ выбора пустого набора.

Назовите простое маленькое, если оно 19 или меньше, а другое - в противном случае. Обратите внимание, что целые числа 500 или менее делятся не более чем на одно большое простое (с кратностью). Маленькие простые числа более проблематичны. То, что мы собираемся сделать, - вычислить для каждой возможной небольшой части простой факторизации LCM (т.е. Одного из состояний ~ 70 000) сумма LCM для проблемы, полученная путем отбрасывания целых чисел, которые не могут делить такой LCM и оставляя только большой простой коэффициент (или 1) для других целых чисел.

Например, если вход 2, 30, 41, 46 и 51, а состояние равно 2, то мы сохраняем 2 как 1, отбрасываем 30 (= 2 * 3 * 5, 3 и 5 малы), удерживайте 41 как 41 (41 большое), удерживайте 46 как 23 (= 2 * 23, 23 велико) и отбросьте 51 (= 3 * 17; 3 и 17 малы). Теперь мы вычисляем сумму LCM с использованием ранее описанной методики. Используйте включение-исключение, чтобы избавиться от подмножеств, чей LCM, чья малая часть правильно делит состояние, а не точно равна. Возможно, я получу полный пример позже.

Ответ 3

What is meant by these states?

Я думаю, здесь здесь говорится, что число находится в множестве B = {b0, b1,..., bk-1} из LCM множества A.

Does dp stand for dynamic programming and if so, what recurrence relation is being solved?

Полагаю, что

dp в эскизе решения означает динамическое программирование.

How is dp[i] computed from dp[i-1]?

Понятно, что мы можем определить состояние следующей группы LCM из предыдущих состояний. Итак, нам нужен только массив из 2 и переключаться взад и вперед.

Why do the big primes not contribute to the number of states? Each of them occurs either 0 or 1 times. Should the number of states not be multiplied by 2 for each of these primes (leading to a non-feasible state space again)?

Мы можем использовать Prime Factorization и exponents только для представления числа.

Вот один пример.

6 = (2 ^ 1) (3 ^ 1) (5 ^ 0) → состояние "1 1 0" для представления 6 18 = (2 ^ 1) (3 ^ 2) (5 ^ 0) → состояние "1 2 0" для представления 18

Вот как мы можем получить LMC 6 и 18 с использованием Prime Factorization

LCM (6,18) = (2 ^ (max (1,1)) (3 ^ (max (1,2)) (5 ^ max (0,0)) = (2 ^ 1) (3 ^ 2) (5 ^ 0) = 18

2 ^ 9 > 500, 3 ^ 6 > 500, 5 ^ 4 > 500, 7 ^ 4 > 500, 11 ^ 3 > 500, 13 ^ 3 > 500, 17 ^ 3 > 500, 19 ^ 3 > 500

мы можем использовать только число показателей простого числа 2,3,5,7,11,13,17,19 для представления LCM в множестве B = {b0, b1,..., bk-1} для данного множества A = {a0, a1,..., aN-1} (1 ≤ N ≤ 100), с 2 ≤ ai ≤ 500.

9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 <= 70000, поэтому нам нужны только два из dp [9] [6] [4] [4] [3] [3] [3 ] [3] для отслеживания всех состояний LCM. Итак, достаточно dp [70000] [2].

Я собрал небольшую программу на С++, чтобы проиллюстрировать, как мы можем получить сумму LCM данного набора A = {a0, a1,..., aN-1} (1 ≤ N ≤ 100), с 2 ≤ ai ≤ 500. В эскизе решения нам необходимо пройти через 70000 максимум из LCM.

int gcd(int a, int b) {
    int remainder = 0;
    do {
        remainder = a % b;
        a = b;
        b = remainder;
    } while (b != 0);
    return a;
}

int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return (a * b) / gcd(a, b);
}


int sum_of_lcm(int A[], int N) {

    // get the max LCM from the array
    int max = A[0];
    for (int i = 1; i < N; i++) {
        max = lcm(max, A[i]);
    }
    max++;

    //
    int dp[max][2];
    memset(dp, 0, sizeof(dp));
    int pri = 0;
    int cur = 1;

    // loop through n x 70000
    for (int i = 0; i < N; i++) {
        for (int v = 1; v < max; v++) {
            int x = A[i];
            if (dp[v][pri] > 0) {
                x = lcm(A[i], v);
                dp[v][cur] = (dp[v][cur] == 0) ? dp[v][pri] : dp[v][cur];
                if ( x % A[i] != 0 ) {
                    dp[x][cur] += dp[v][pri] + dp[A[i]][pri];
                } else {
                    dp[x][cur] += ( x==v ) ? ( dp[v][pri] + dp[v][pri] ) : ( dp[v][pri] ) ;
                }
            }
        }
        dp[A[i]][cur]++;
        pri = cur;
        cur = (pri + 1) % 2;
    }

    for (int i = 0; i < N; i++) {
        dp[A[i]][pri] -= 1;
    }
    long total = 0;
    for (int j = 0; j < max; j++) {
        if (dp[j][pri] > 0) {
            total += dp[j][pri] * j;
        }
    }
    cout << "total:" << total << endl;

    return total;
}



int test() {
    int a[] = {2, 6, 7 };
    int n = sizeof(a)/sizeof(a[0]);
    int total = sum_of_lcm(a, n);
    return 0;
}

Output
total:104

Ответ 4

Состояния - это больше, чем степеней простых чисел. У вас есть номера до 2 ^ 8, поэтому мощность 2 находится в [0..8], что составляет 9 состояний. Аналогично для других состояний.

"dp" вполне может стоять за динамическое программирование, я не уверен.

Рекуррентное отношение является сердцем проблемы, поэтому вы узнаете больше, решив его самостоятельно. Начните с небольших, простых примеров.

Для больших простых чисел попробуйте решить проблему, не используя их (или их эквиваленты), а затем добавьте их обратно, чтобы увидеть их влияние на конечный результат.