Дискретное логарифмирование

Простая

Ограничение по времени выполнения 8 секунд

Ограничение по использованию памяти 256 мегабайт

Даны натуральные числа a, b, n.

Требуется найти дискретный логарифм b по основанию a по модулю n, то есть такое число x (0 ≤ x < n), что a^x ≡ b (mod n).

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

В первой строке входного файла заданы через пробел три целых числа a, b и n (0 ≤ a, b, n ≤ 10^12), n ≠ 0.

В первой строке выходного файла выведите -1, если дискретного логарифма не существует. Иначе следует вывести его значение.

Если ответ не однозначен, разрешается выводить любой.

Ввод #1

Ответ #1

Отправки 516

Коэффициент принятия 19 %