Количество закрытых ключей (криптография)?

Question

[Proshka17]

Добрый день!
Есть задачка на программирование:
Зыкрытый ключ задается как (p,q)
Необходимо определить количество подходящих открытых ключей.
Никак не могу придумать алгоритм перебора

Answer 1

[Mercury13]

Разложим НОД и НОК на простые множители.
Для каждого простого определим степень в НОД и НОК.

Если хоть для одного простого a p[НОД,a] > p[НОК,a], STOP: 0.
[ПРИМЕР: НОД=2, НОК=5 — ну не бывает такого, правда? А не бывает из-за того, что в НОД 2¹, а в НОК 2⁰.]

Теперь возьмём другой пример: в НОД 2¹, в НОК 2³. Это значит, в одном числе будет 2¹, в другом 2³ — два варианта.

Итого ответ: 0, если хотя бы для одного простого a будет p[НОК,а] < p[НОД,a]
Иначе 2^{КОЛИЧЕСТВО{простых a} ( p[НОК,а] > p[НОД,a] )}

ПРИМЕР: НОД = 2¹·3⁰·5² = 50, НОК = 2³·3¹·5² = 600
1-2. 1-0-2 = 50, 3-1-2 = 600 и 600-50
3-4. 1-1-2 = 150, 3-0-2 = 200 и 200-150
Правильно, четыре штуки?

UPD. Для большей скорости можно разобрать на простые множители НОК, а в НОД просто проверить то, что получилось: нет ли степени выше, нет ли посторонних простых.
Ну и, конечно, очень крайние случаи: НОД=НОК → 1 штука, НОД>НОК → 0 штук

Comments

[Proshka17]

Не до конца осознал эту строку:
Иначе 2^{КОЛИЧЕСТВО{простых a} ( p[НОК,а] > p[НОД,a] )}
То-есть ответ это 2^(количество простых множителей для которых степень этого простого множителя в НОК больше чем в НОД) ?

[Mercury13]

Да.

[Mercury13]

Proshka17,
1. Map тут только для упрощения кода; оптимум — старый добрый массив на 64 места.
2. Си++11 сильно улучшит жизнь. И даже typedef pair. А то у тебя из Си++11 один auto.
3. Класс возвращает результат в консоль — не комильфо.
4. На других тестах реально работало? Лучше написать как nokm[it->first] - it->second — если, по-твоему, верна именно разность, а не единица.
5. Пока похоже на переполнение в pow.
6. C++17 как-то действующий начиная с 8.0, а стабильный — с 9.0. Хотя у тебя нет 17-го.
7. Не может long long быть произведением 64 разных простых → хватит 2ULL << counter.

[Proshka17]

Mercury13, Добрый день!
Не совсе понимаю, как в pow может быть переполнение?

[Mercury13]

1. Отлично, мы храним это дело неявно. Это главное, и очень хорошее, ваше достижение.
2. nok % nod != 0 — это стоит делать в самом начале, важная проверка.
3. Нечего использовать pow. И учтите, что double меньше long long, и если кто-то накопает большое, сверх 52 битов, простое число — будет wrong result.
4. div++ не годится, стоило бы работать чуть менее топорно.
5. Условие остановки цикла — div² > nok. Это главный вопрос, почему проблемы со временем.
6. Очередной вопрос: остальные тесты верно прошли? Меня напрягает строка nod = nod / (pow((double)div, (double)power)); Мы делим НОД на степень простого множителя в НОК’е, цифру, на которую он, скорее всего, не делится.
7. Я бы сделал функцию testDivisor(): сначала testDivisor(2), потом по всем нечётным до квадратного корня, а потом — то, что осталось от НОК. Это позволит делать и другие мелкие ускорители: например, проверять 2, 3, 5, а затем 6n+1 и 6n+5.
8. Эта функция явно не inline, а значит, её лучше вынести из тела класса.
9. Объект без ООП в стиле Java?
10. Извините, что написал про 2ULL — 1ULL << counter, разумеется.
11. Всё ещё функция возвращает свой результат в консоль — некузяво!

[Mercury13]

Прошли задачи? Тогда можете удалить сработавшие решения и отметить ответы как решение?

[Proshka17]

Mercury13, Добрый день!
Посмотрите пожалуйста этот вопрос:
Как понять условие задачи?
Я не совсем понял как трактовать условие задачи.