Недавно у одного известного исполнителя появилась новая песня. Он хочет загрузить её в…
- User
Недавно у одного известного исполнителя появилась новая песня. Он хочет загрузить её в VK Музыку. Перед пиар-менеджером встала задача — выбрать длительность в секундах для трека, который в итоге будет представлен в VK Музыке.
В оригинале песня длится t секунд. Можно изменить её не более чем на d секунд, при это длительность песни должна являться натуральным числом. И главное, поскольку это число должно быть красивым, то длительность также должна иметь не более трёх делителей.
Посчитайте количество способов выбрать длительность трека, с учётом двух перечисленных выше условий.
Формат входных данных В первой строке содержится одно целое число t (1≤t≤5∗1013). Во второй строке содержится одно целое число d (1≤d≤5∗106).
Формат выходных данных Выведите одно целое число - количество способов выбрать длительность трека. Пример 1
Входные данные
4 6
Выходные данные
7
Пример 2 Входные данные
180 30
Выходные данные
12
кол во делителей находи так:
import math def numd(n): counter = 0 for i in range(1, math.isqrt(n) + 1): if n % i == 0: counter += 1 if i * i != n: counter += 1 return counter - Assistant
Чтобы решить эту задачу, необходимо определить количество натуральных чисел в интервале ([t - d, t + d]), которые имеют не более трёх делителей. Такие числа могут быть:
- 1 — имеет ровно один делитель.
- Простые числа — имеют ровно два делителя.
- Квадраты простых чисел — имеют ровно три делителя.
Таким образом, наша задача сводится к следующему:
- Проверить, входит ли число 1 в заданный интервал.
- Найти все простые числа в этом интервале.
- Найти все квадраты простых чисел в этом интервале.
Для эффективного поиска простых чисел в большом диапазоне можно использовать решето Эратосфена и сегментированное решето. Вот пример реализации на Python:
import sys import math def input(): return sys.stdin.read() def sieve(limit): is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False for num in range(2, int(math.isqrt(limit)) + 1): if is_prime[num]: for multiple in range(num*num, limit +1, num): is_prime[multiple] = False primes = [num for num, prime in enumerate(is_prime) if prime] return primes def count_primes_in_range(L, R, primes): # Создаём булевый массив для сегментированного решета segment_size = R - L + 1 is_prime_segment = [True] * segment_size for p in primes: start = max(p*p, ((L + p -1)//p)*p) for multiple in range(start, R +1, p): is_prime_segment[multiple - L] = False if L == 1: is_prime_segment[0] = False # 1 не является простым primes_in_range = [L + i for i, is_p in enumerate(is_prime_segment) if is_p] return primes_in_range def main(): data = input().split() t = int(data[0]) d = int(data[1]) L = max(1, t - d) R = t + d sqrt_R = int(math.isqrt(R)) + 1 small_primes = sieve(sqrt_R) primes_in_range = count_primes_in_range(L, R, small_primes) count = len(primes_in_range) # Найдём квадраты простых чисел в диапазоне # Нужно проверить, что p*p в [L,R], где p — простое prime_squares = 0 for p in small_primes: p_sq = p * p if L <= p_sq <= R: prime_squares +=1 # Проверим, входит ли 1 в диапазон if L <=1 <=R: count +=1 # Итоговое количество: простые числа + квадраты простых + 1 (если 1) total = count + prime_squares print(total) if __name__ == "__main__": main()Объяснение кода:
-
Функция
sieve(limit): Реализует классическое решето Эратосфена для поиска всех простых чисел до заданногоlimit. Возвращает список найденных простых чисел. -
Функция
count_primes_in_range(L, R, primes): Использует сегментированное решето для поиска всех простых чисел в диапазоне ([L, R]), используя ранее найденные простые числа до (\sqrt{R}). -
Функция
main():- Считывает входные данные
tиd. - Определяет границы диапазона ([L, R]).
- Находит все простые числа до (\sqrt{R}) с помощью
sieve. - Находит все простые числа в диапазоне ([L, R]) с помощью
count_primes_in_range. - Находит количество квадратов простых чисел в диапазоне.
- Проверяет, входит ли число 1 в диапазон.
- Выводит итоговое количество допустимых чисел.
- Считывает входные данные
Пример работы:
Рассмотрим пример 1:
Входные данные: 4 6 Выходные данные: 7Пояснение:
Диапазон ([4-6, 4+6] = [1, 10]).
Допустимые числа:
- 1 (1 делитель)
- 2, 3, 5, 7 (простые числа)
- 4 (квадрат простого числа 2)
- 9 (квадрат простого числа 3)
Всего 7 чисел.
Оптимизация:
- Сегментированное решето позволяет эффективно находить простые числа в больших диапазонах, не требуя большого объёма памяти.
- Использование списка предварительных простых чисел до (\sqrt{R}) ускоряет процесс отбора простых чисел в основном диапазоне.
Этот подход гарантирует, что решение будет работать эффективно даже при больших значениях ( t ) и ( d ) в пределах заданных ограничений.