Условие
RSA++
Тур I, задача 4
Исследовательский отдел министерства обороны Байтландии разработал новый сверхнадежный алгоритм шифрования. Назвать новый алгоритм решили RSA++, так как за его основу был взят знаменитый алгоритм RSA.
Как известно, в основе алгоритма RSA лежит использование пары простых натуральных чисел P и Q и производного числа N = P * Q. Числа P и Q называются ключами шифрования, а число N – модулем шифрования. Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.
Принципиальным отличием нового RSA++ алгоритма от RSA алгоритма состоит в выборе ключей. Если в реализации RSA алгоритма требуется пара простых чисел P и Q, то в RSA++ алгоритме числа P и Q должны быть взаимно простыми. Два натуральных числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме единицы.
Для анализа надежности нового алгоритма ученые хотят узнать количество различных пар ключей P и Q, таких, что 1 < P < Q и соответствующий им модуль шифрования удовлетворяет условию: N ≤ K. Ваша задача помочь ученым в решении этого нелегкого вопроса.
Входные данные Первая строка входного файла содержит одно целое число K (1 ≤ K ≤ 109).
Выходные данные Выходной файл должен содержать одно целое число – количество различных пар ключей P и Q.
input.txt
output.txt
Примечание
12
3
(2,3); (2,5); (3,4)
18
6
(2,3);(2,5);(2,7);(2;9);(3,4);(3;5)
Решение
Давайте перебирать первое число до √n.
Выберем диапазон, в котором лежит следующее число.
И тогда задача сводится к следующей : найти все числа в промежутке 1..n взаимно простые с текущим.
Давайте выпишем список всех различных делителей числа, их будет не больше 6.
Переберём все числа, которые можно получить перемножением каких либо делителей. Для этого переберём все подмаски списка делителей, посмотрим на числа, которые получаются при перемножении чисел на позициях, где стоят 1.Посмотрим кол-во чисел на отрезке, которые делятся на текущее. Если кол-во единиц в маске чётное, прибавим к переменной кол-во делящихся чисел на отрезке, а иначе отнимем.
В конце алгоритма получаем кол-во чисел не взаимно простых с текущим числом.
И пользуясь методом включений-исключений получаем ответ.
Примерная асимптотика О(√n(2^6+⁴√n))
