Недавно у одного известного исполнителя появилась новая песня. Он хочет загрузить её в VK Музыку. Перед пиар-менеджером встала задача — выбрать длительность в секундах для трека, который в итоге будет представлен в VK Музыке. В оригинале песня длится t секунд. Можно изменить её не более чем на d секунд, при это длительность песни должна являться натуральным числом. И главное, поскольку это число должно быть красивым, то длительность также должна иметь не более трёх делителей. Посчитайте количество способов выбрать длительность трека, с учётом двух перечисленных выше условий. Система оценки Группа тестов Дополнительные ограничения Баллы Необходимые группы 1 t≤106,d≤104 10 — 2 t≤109,d≤105 35 1 3 t≤2⋅107,d≤5⋅106 30 1 4 t≤5⋅1013,d≤5⋅106 25 1−3 Формат входных данных В единственной строке содержатся два целых числа, разделённых пробелом t и d. (1≤t≤5⋅1013, 1≤d≤5⋅106). Формат выходных данных Выведите одно целое число - количество способов выбрать длительность трека.

Кадру задачи: требуется посчитать количество допустимых длительностей x в диапазоне [t − d, t + d], x — натуральное число, и число делителей d(x) не более 3.

Идея решения (важно понять, какие числа подходят):

• Число x имеет не более 3 делителей тогда, когда x равно:
  • 1 (у него 1 делитель),
  • простое число p (делителей 1 и p — всего 2),
  • квадрат простого числа p^2 (делителей 1, p, p^2 — всего 3).
• Другие числа (например, произведения двух разных простых pq, степени p^k с k≥3 и т.д.) имеют больше 3 делителей и не подходят.

Следовательно, нужно посчитать в диапазоне [L, R], где L = max(1, t − d), R = t + d, сколько чисел являются:

• 1,
• простыми,
• квадратами простых чисел (то есть p^2, где p — простое).

Как посчитать это efficiently для больших t (до 5⋅10^13) и d (до 5⋅10^6):

1. Определим L и R:

   • L = max(1, t − d)
   • R = t + d

2. 1 в диапазоне учитываем отдельно: если L ≤ 1 ≤ R, то прибавляем 1 к ответу.

3. Простые в диапазоне [L, R]:

   • Используем чередование двух этапов: a) Сначала находим все простые числа до sqrt(R) обычным решетом Эратосфена. Это даст набор базовых простых p, которые нужны для проверки больших интервалов. b) Затем применяем сегментированный решет Эратосфена к диапазону [L, R]:
     • создаем массив is_prime_segment длиной R − L + 1, заполняем True (потенциально простые),
     • для каждого базового простого p помечаем все его кратные в [L, R] как составные,
     • после этого считаем сколько позиций i имеют True и число (L + i) ≥ 2.
   • Количество простых в [L, R] — это prime_count.

   Примечание: размер диапазона не превосходит 2d + 1 ≤ 10^7 + 1, что приемлемо для сегментированного sieve.

4. Квадраты простых p^2 в диапазоне:

   • Нужно посчитать простые p такие, что p^2 ∈ [L, R].
   • Это эквивалентно p ∈ [p_min, p_max], где:
     • p_min = минимальное p с p^2 ≥ L, то есть p_min = ceil_sqrt(L),
     • p_max = максимальное p с p^2 ≤ R, то есть p_max = floor_sqrt(R).
   • Количество таких p — это количество простых p в диапазоне [p_min, p_max].
   • Для этого удобно иметь тот же массив простых до sqrt(R). Можно просто пройти по p в этом диапазоне и проверить, простое ли число p, используя ранее построенный базовый sieve.

5. Итог: ответ = (1 если L ≤ 1 ≤ R иначе 0) + prime_count + prime_square_count.

Преимущества и сложности:

• Диапазон [L, R] имеет длину не более 2d + 1 ≤ 10^7 + 1, что приемлемо для сегментированного sieve.
• Порог для проверки простоты — sqrt(R) ≈ sqrt(5⋅10^13) ≈ 7.1⋅10^6, значит базовый sieve до примерно 7.5⋅10^6 нужен и вычислительно выполним.
• Подсчет prime_square_count не требует дополнительного сложного алгоритма: достаточно знать, какие p в нужном диапазоне являются простыми (эту информацию можно получить из базового sieve).

Пример иллюстративный (для понимания): Пусть t = 10, d = 3.

• L = max(1, 10 − 3) = 7, R = 10 + 3 = 13.
• 1 не входит.
• Простые в [7,13]: 7, 11, 13 — три числа.
• p^2 в [7,13]: 9 = 3^2 — одно число (здесь 3 — простое).
• Ответ = 0 + 3 + 1 = 4.

Алгоритм в виде псевдокода (упрощенный, без привязки к конкретному языку):

• Ввод t, d

• L = max(1, t − d)

• R = t + d

• contains_one = (L ≤ 1 ≤ R) ? 1 : 0

• max_s = floor_sqrt(R)

• Сначала построим базовый массив is_prime_up_to_max_s с помощью обычного решета Эратосфена.

• Соберем список primes_base = все p ≤ max_s, где is_prime_up_to_max_s[p] = true.

• Сегментированный sieve для [L, R]: seg_size = R − L + 1 is_prime_seg[0..seg_size−1] = true Для каждого p в primes_base: start = max(p*p, ceil(L / p) * p) for x from start to R step p: is_prime_seg[x − L] = false prime_count = 0 for i = 0..seg_size−1: if (L + i) ≥ 2 и is_prime_seg[i] = true: prime_count += 1

• Подсчет prime_square_count: p_min = ceil_sqrt(L) p_max = floor_sqrt(R) prime_square_count = 0 если p_min ≤ p_max: для p от p_min до p_max: если is_prime_up_to_max_s[p] = true: prime_square_count += 1

• Ответ = contains_one + prime_count + prime_square_count

• Вывести ответ

Замечания по реализации:

• Для повышения производительности в реальном коде используйте типы данных и структуры, экономящие память:
  • сегментный массив is_prime_seg можно держать как битовый или байтовый массив (bytearray в Python или vector в C++).
  • базовый sieve до max_s можно держать как массив байтов (0/1).
• Убедитесь, что при вычислении start для отметки множителей учитывается, что если L ≤ p, то старт не должен быть равен p самого числа в диапазоне (чтобы не пометить p как составное).

Временная сложность:

• Построение базового sieve до max_s: O(max_s log log max_s).
• Сегментированный sieve по диапазону длины ≈ 2d: примерно O((R − L + 1) log log max_s) с учетом количества базовых простых.
• Подсчет prime_square_count занимает O(p_max − p_min + 1) при необходимости, но этот диапазон ≤ floor_sqrt(R) − ceil_sqrt(L) + 1 и обычно меньше, чем размер сегмента.

Эта стратегия удовлетворяет требованиям задачи даже в наихудшем допустимом диапазоне: d ≤ 5⋅10^6, t ≤ 5⋅10^13.