1 Отредактировано yury (2020-06-19 15:00:26)

Тема: Вопрос по поводу формулы включения-исключения

Статья на сайте  -
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)

На интервале, равном НОК, таких отрезков, где все идущие подряд числа кратны хотя бы одному заданному, - несколько.

Как узнать длину вычеркнутого отрезка максимально возможного размера, при произвольно заданном списке взаимно простых чисел - на которые должны делиться эти идущие подряд элементы ?

Можно ли решать эту задачу с помощью формулы включения-исключения?