406795: GYM102558 B Закрытый ключ

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Закрытый ключограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Во всех крупных IT-компаниях немалое внимание уделяется вопросам информационной безопасности, и Яндекс  — не исключение

Дима и Егор разрабатывают новый сервис YD (Yandex Dorogi) и в данный момент проводят аудит его безопасности. Для шифрования пользовательских данных в YD используется алгоритм шифрования с открытым ключом YS (Yandex Shifrovatel).

Схема работы YS такова: для каждого сервиса генерируется закрытый ключ ($$$p, q$$$), где $$$p$$$ и $$$q$$$ — натуральные числа. По закрытому ключу ($$$p, q$$$) генерируется открытый ключ (НОД($$$p, q$$$), НОК($$$p, q$$$)), который доступен всем пользователям. Если злоумышленник сможет по открытому ключу получить закрытый ключ, то он получит доступ ко всем данным YD и принесет сервису непоправимый вред. Конечно же, Егор и Дима не могут этого допустить, поэтому они хотят сделать так, чтобы злоумышленнику пришлось перебрать очень много вариантов открытого ключа, прежде чем он сможет его угадать.

Дима уже сгенерировал закрытый ключ для YD и получил на его основе открытый ключ ($$$x, y$$$). Егору сразу же стало интересно, сколько вариантов закрытого ключа придётся перебрать злоумышленнику для взлома YD в худшем случае, иными словами, сколько существует закрытых ключей ($$$p, q$$$) таких, что открытым ключом для них является ($$$x, y$$$). К сожалению, у Егора есть много других задач, очень важных для запуска YD, поэтому он просит вас вычислить это количество за него.

Входные данные

В первой строке содержатся два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq y \leq 10^{12}$$$) — описание открытого ключа.

Выходные данные

Выведите одно целое число — количество закрытых ключей, для которых данный ключ является открытым.

ПримерыВходные данные
5 10
Выходные данные
2
Входные данные
10 11
Выходные данные
0
Входные данные
527 9486
Выходные данные
4
Примечание

В первом примере существует два закрытых ключа, для которых ($$$5, 10$$$) является открытым ключом: ($$$5, 10$$$) и ($$$10, 5$$$).

Во втором примере Дима ошибся, потому что ни один закрытый ключ не порождает открытый ключ ($$$10, 11$$$).

В третьем примере подходящими закрытыми ключами являются ($$$527, 9486$$$), ($$$1054, 4743$$$), ($$$4743, 1054$$$), ($$$9486, 527$$$).

НОД (наибольшим общим делителем) двух натуральных чисел $$$p$$$ и $$$q$$$ называется наибольшее число $$$k$$$ такое, что $$$p$$$ делится на $$$k$$$ и $$$q$$$ делится на $$$k$$$. Например, НОД($$$6, 15$$$) равен $$$3$$$, а НОД($$$16, 8$$$) равен $$$8$$$.

НОК (наименьшим общим кратным) двух натуральных чисел $$$p$$$ и $$$q$$$ называется наименьшее число $$$k$$$ такое, что $$$k$$$ делится на $$$p$$$ и $$$k$$$ делится на $$$q$$$. Например, НОК($$$2, 3$$$) равен $$$6$$$, а НОК($$$10, 20$$$) равен 20.

加入题单

上一题 下一题 算法标签: