Тема: Вопрос по поводу формулы включения-исключения
Статья на сайте -
https://e-maxx.ru/algo/inclusion_exclus … 3cj4STgYBE
Есть задача, аналогичная некоторым примерам, приведенным в данной статье.
Но как-то не получается ее сформулировать с применением формулы включения-исключения.
Хотя, мне кажется, что она должна относиться к этой области.
Обычно, с помощью формулы ВКЛ-ИСКЛ ищут количество элементов некоторого множества, обладающих заданными свойствами.
Но вот нигде не встречал вариант, когда надо найти количество элементов некоторого множества, не просто обладающих заданными свойствами сами по себе, а еще и взаимосвязанных с другими элементами в этом же множестве.
"Количество чисел в заданном отрезке, кратных хотя бы одному из заданных чисел"
- очень похожая задача, только мне надо найти длину интервалов внутри заданного отрезка, где "кратные хотя бы одному из заданных чисел" - расположены подряд, без промежутков.
Например, возьмем ряд нечетных чисел, от 1 до 211.
Надо найти последовательности идущих подряд элементов этого ряда, кратных хотя бы одному из чисел 3, 5, 7 - максимально возможной длины.
Максимальная длина, равная 4 элемента подряд, встречается в этом ряду два раза - 3-5-7-9, и 201-203-205-207.
Другие отрезки могут быть только меньше (длиной 3, 2, 1)
На интервале, равном НОК, таких отрезков, где все идущие подряд числа кратны хотя бы одному заданному, - несколько.
Как узнать длину вычеркнутого отрезка максимально возможного размера, при произвольно заданном списке взаимно простых чисел - на которые должны делиться эти идущие подряд элементы ?
Можно ли решать эту задачу с помощью формулы включения-исключения?