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

Штрихи на рейке

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

Столяр размечает рейку. Сначала делит её пополам и ставит карандашом штрих посередине. Потом делит на три равные части и ставит два штриха, потом на четыре — и так до n равных частей. Концы рейки он не отмечает, а если новый штрих приходится точно на старый, второй раз не рисует: при делении на четыре середина уже отмечена, и новых штрихов только два.

Сколько штрихов окажется на рейке? Столяр ещё не решил, на сколько частей делить в последний раз, поэтому посчитайте ответ для нескольких n.

Вход

В первой строке число вопросов q (1 ≤ q ≤ 10⁵). Дальше q чисел n по одному в строке (1 ≤ n ≤ 10⁶).

Выход

Для каждого n — число различных штрихов после делений на 2, 3, …, n частей. При n = 1 рейку не делили, и штрихов нет.

Примеры

Пример 1

Вход

Выход

Ограничения

Время · Python: 5000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

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

1Подсказка 1

Штрих при делении на b частей стоит в точке a/b. Когда два штриха совпадают? Запишите дробь, которая описывает штрих, так, чтобы у одного штриха была ровно одна запись.

2Подсказка 2

Каждый штрих — несократимая дробь a/b с 0 < a < b ≤ n. Сколько таких дробей с данным знаменателем b? У этого числа есть имя.

3Идея

Штрих в точке a/b совпадает со штрихом при меньшем числе частей ровно тогда, когда дробь сокращается. Поэтому штрих впервые появляется при делении на b частей, где b — знаменатель несократимой дроби, и новых штрихов при делении на b столько, сколько чисел от 1 до b взаимно просты с b. Это функция Эйлера φ(b). Ответ — φ(2) + φ(3) + … + φ(n). Значения φ для всех чисел до 10⁶ сразу даёт решето, ответы на запросы — префиксные суммы.

4Разбор

Если b = p₁^k₁ ⋯ p_r^k_r, то φ(b) = b · (1 − 1/p₁) ⋯ (1 − 1/p_r). Отсюда решето: заводим phi[b] = b и для каждого простого p проходим по его кратным, заменяя phi[m] на phi[m] − phi[m] / p. Деление здесь всегда нацело: к моменту обработки p в phi[m] уже учтены только другие простые делители, и множитель p в нём сохранился. В Python это одна строка со срезом: phi[p::p] = [v - v // p for v in phi[p::p]].

В решении на Go — линейное решето: φ(p · i) = φ(i) · p, если p делит i, и φ(i) · (p − 1) иначе. Каждое число получает значение один раз.

Дальше префиксные суммы total[n] = phi[2] + … + phi[n], и каждый запрос — одно обращение к массиву. При n = 10⁶ ответ 303 963 552 391 — в 32 бита он не помещается.

Можно проверить себя на маленьком: при n = 4 штрихи — 1/2, 1/3, 2/3, 1/4, 3/4, всего 5 = φ(2) + φ(3) + φ(4) = 1 + 2 + 2.

4+Решение

5Сложность

Решето для φ — O(n log log n) или O(n) для линейного, префиксные суммы — O(n), запросы — O(1) каждый. Память — O(n).

6Типичные ошибки

Считать штрихи «в лоб». Сложить b − 1 по всем делениям — значит посчитать совпавшие штрихи много раз: уже на первом примере вместо 11 получится 15.
φ каждого числа перебором делителей. Формула верная, но это около n√n операций — сотни миллионов для n = 10⁶.
НОД для каждой пары. Проверять gcd(a, b) = 1 для всех пар — уже квадрат, 5·10¹¹ пар.
Переполнение. Сумма до 10⁶ около 3·10¹¹.

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

NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Алгоритм Евклида Наибольший общий делитель двух чисел за O(log n) делений с остатком. O(log min(a, b)) 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи