Ctrl K

Сумма целых частных всех пар

Сложная
Дан массив положительных целых чисел values. Для каждой упорядоченной пары индексов (i, j) — включая пары с i = j — возьмите целую часть от деления values[i] на values[j] (деление с округлением вниз). Верните сумму всех этих частных по модулю 10⁹ + 7.
Пример 1
values=[3, 7, 4] → 7

Пары с ненулевым частным: 3/3, 7/7, 4/4 дают по 1; 7/3 = 2; 4/3 = 1; 7/4 = 1. Сумма 3 + 2 + 1 + 1 = 7.

Пример 2
values=[6, 6, 6] → 9

Все девять упорядоченных пар дают частное 1.

Пример 3
values=[1, 100000] → 100002
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНОД пар по номеру в сортировке СложнаяСамый доходный участок под лимитом СложнаяСамый тяжёлый день чтения СложнаяЛучшее среднее длинного отрезка СложнаяКороткий отрезок с нужной суммой Сложная
загружаем Python…
Вход
values=[3, 7, 4]
Ожидается
7

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