Solve the Exponent
Find the smallest non-negative x with Ax ≡ B (mod M), where M is prime, or −1 if no solution exists.
Input: one line with three integers A, B, M.
Output: the smallest x, or −1.
Constraints:
- 2 ≤ M ≤ 107, M prime
- 0 ≤ A, B < M
Sample Tests
Input 1
2 9 11
Output 1
6
Input 2
3 1 7
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.