Войти Регистрация
Алгоритмы

180. Сколько вариантов фасовки кратны номеру ячейки

Лёгкая

Даны списки l и r длины n. Для ячейки с номером i (нумерация с 1) выбирают число a_i, где l_i ≤ a_i ≤ r_i и a_i делится на i.

Верните число различных массивов a по модулю 10⁹ + 7. Если хоть для одной ячейки подходящего числа нет — ответ 0.

В работе: Планирование фасовки: в i-ю секцию стеллажа товар кладут упаковками по i штук, а лимиты по секциям разные.

Пример 1

Ввод
l = [1, 2, 3]
r = [2, 4, 3]
Вывод
4

1-я ячейка: 1 или 2, 2-я: 2 или 4, 3-я: 3. Всего 2 · 2 · 1 = 4.

Пример 2

Ввод
l = [1, 3]
r = [5, 3]
Вывод
0

Во 2-й ячейке только 3, оно не делится на 2 — вариантов нет.

Ограничения

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ l_i ≤ r_i ≤ 10⁹
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def count_arrays(l, r):
МатематикаКомбинаторикаОстаток от деленияцельO(n)

Источник: Ozon, отборочный контест Route 256, 2024 (репозиторий участника). Условие пересказано своими словами.