Ctrl K

Отрезки с заданным НОК

Средняя
Дан массив натуральных чисел values и число multiple. Посчитайте, у скольких непустых отрезков (подряд идущих кусков массива) наименьшее общее кратное всех элементов равно ровно multiple. НОК набора чисел — наименьшее натуральное число, которое делится на каждое из них. Отрезки с разными границами считаются разными.
Пример 1
values=[2, 3, 4, 6, 5], multiple=12 → 5

НОК 12 у отрезков [2, 3, 4], [3, 4], [3, 4, 6] и [2, 3, 4, 6], а также у [4, 6]. Всё, что содержит 5, даёт НОК, кратный 5.

Пример 2
values=[5], multiple=10 → 0

Единственный отрезок [5] имеет НОК 5, а не 10.

Пример 3
values=[1, 3, 1, 3], multiple=3 → 8
Ограничения
  • 1 ≤ len(values) ≤ 1000
  • 1 ≤ values[i] ≤ 1000
  • 1 ≤ multiple ≤ 1000
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПростые числа до границы СредняяРамки одной формы СредняяОтрезки на графике СредняяКуски с общим делителем СредняяОтрезки с заданным НОД Средняя
загружаем Python…
Вход
values=[2, 3, 4, 6, 5], multiple=12
Ожидается
5

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 108 тестов на сервере, включая скрытые.