eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 8 секунд
Ліміт використання пам'яті 256 MiB

Задано натуральні числа a, b, n.

Потрібно знайти дискретний логарифмb за основою a по модулю n, тобто таке число x (0x < n), що a^x ≡ b (mod n).

Вхідні дані

У першому рядку вхідного файлу задано через пропуск три цілих числа a, b та n (0a, b, n10^12), n0.

Вихідні дані

У першому рядку вихідного файла виведіть -1, якщо дискретного логарифма не існує. Інакше слід вивести його значення.

Якщо відповідь не однозначна, дозволяється вивести довільну.

Приклад

Вхідні дані #1
2 4 6
Вихідні дані #1
2