Задачі
Дискретне логарифмування
Дискретне логарифмування
Задано натуральні числа 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
2 4 6
Вихідні дані #1
2