Шифр караван-сарая Таш-Рабат


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Хранитель караван-сарая Таш-Рабат запирает сундук с шёлком на хитрый замок. Замок хранит три числа a, b, m и открывается кодом x — неотрицательным целым числом, для которого остаток от деления a^x на m равен остатку от деления b на m:

a^x ≡ b (mod m).

Считается, что a⁰ = 1. Хранитель забыл код, но помнит, что выбирал наименьший подходящий.

Рисунок

Для каждого из T замков найдите наименьшее x ≥ 0 или сообщите, что замок открыть нельзя.

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

В первой строке — число T (1 ≤ T ≤ 300). В каждой из следующих T строк — три целых числа a b m (0 ≤ a, b ≤ 10⁹, 1 ≤ m ≤ 10⁹). Число m не обязательно простое, а a и m не обязательно взаимно просты.

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

Для каждого замка выведите наименьший код или -1, если подходящего кода нет.

Пример 1

Вход:

5
3 1 16
3 11 16
2 0 12
6 0 36
5 3 1

Выход:

0
3
-1
2
0

Пояснение

Для замка 3 1 16 ответ 0, ведь 3⁰ = 1. Для замка 3 11 16: 3³ = 27 = 16 + 11, а меньшие степени дают остатки 1, 3, 9 — ответ 3. Для замка 2 0 12 кода нет: степени двойки по модулю 12 — это 1, 2, 4, 8, 4, 8, … Для 6 0 36: 6² = 36 ≡ 0, ответ 2. По модулю 1 любые числа сравнимы, поэтому для последнего замка ответ 0.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 3000.


Комментарии

Еще нет ни одного комментария.