CS
Задачник Базовый курс EN

Задача

Сколько раз выполнится строка

оценка подсчёт вариантов теория чисел олимпиады

Сколько раз выполнится строка count += 1 в этой программе?

count = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        count += 1

Это та самая программа из викторины в статье: внутренний цикл перебирает числа, кратные i. Ответьте для нескольких n, вплоть до 10¹¹. Запустить её и посчитать не выйдет: оцените сначала, сколько шагов она сделает при таком n.

Вход

В первой строке t (1 ≤ t ≤ 10), дальше t чисел n (1 ≤ n ≤ 10¹¹), по одному в строке.

Выход

Для каждого n — сколько раз выполнится строка.

Примеры

Пример 1

Вход
5
1
2
3
10
100
Выход
1
3
5
27
482

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

При фиксированном i внутренний цикл делает ⌊n/i⌋ шагов, так что ответ — сумма ⌊n/1⌋ + ⌊n/2⌋ + … + ⌊n/n⌋. Но сто миллиардов слагаемых — это минуты даже на Go. Подумайте, что считает эта сумма: сколько пар (i, j)?

2Идея

Каждый шаг внутреннего цикла — это число j = i·k, то есть пара натуральных (i, k) с i·k ≤ n. Ответ — число целых точек под гиперболой x·y = n. Гипербола симметрична относительно прямой x = y, и почти все точки лежат в двух «рукавах» вдоль осей: у каждой точки хотя бы одна координата не больше √n.

3Разбор

Пусть k = ⌊√n⌋. Точек с x ≤ k ровно ⌊n/1⌋ + … + ⌊n/k⌋, и столько же — с y ≤ k. Точки, у которых обе координаты не больше k, — квадрат k × k — посчитаны дважды. Значит,

$$\sum_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor = 2\sum_{i=1}^{k} \left\lfloor \frac{n}{i} \right\rfloor - k^2.$$

Это приём Дирихле с гиперболой. Теперь слагаемых всего √n ≈ 3,2·10⁵ на запрос вместо 10¹¹. Корень берите в целых числах — math.isqrt в Python, а в Go поправьте результат math.Sqrt на ±1, чтобы ошибка округления не сдвинула k.

Заодно стоит заметить, во что это выливается: ответ растёт как n ln n. Для n = 10¹¹ это 2,5·10¹² — значит, сама программа из условия на Go шла бы минуты, а на Python — около полусуток.

3+Решение
4Сложность

O(√n) на запрос: при n = 10¹¹ это 3,2·10⁵ делений.

5Типичные ошибки
  • Сумма по всем i. Верно, но O(n): при n = 10⁸ уже секунды на Python, при 10¹¹ — часы.
  • Корень в числах с плавающей точкой. Для n = k² − 1 приближённый корень может округлиться до k, и формула посчитает лишнее. Шестой тест — ровно такие n.
  • 32-битные целые. Ответ доходит до 2,5·10¹².

Алгоритмы задачи

TEC Приём O-большое Как растёт работа вместе с данными: O, Ω и Θ, правила оценки кода и где асимптотика обманывает. оценка — по тексту программы 1 задача TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача
Каталог алгоритмов