Modular Inverse
mediumMath & Number Theory+20 XPTime limit 2s
The modular inverse of a modulo m is the number x with 0 ≤ x < m such that (a · x) mod m = 1. For example the inverse of 3 modulo 11 is 4, because 3 · 4 = 12 and 12 mod 11 = 1.
The modulus is not always prime. An inverse exists only when a and m share no common factor; otherwise print -1.
Input:
- line 1:
q - next
qlines: two integersa m
Output: q lines — the inverse of a modulo m, or -1 if it doesn't exist.
Constraints: 1 ≤ q ≤ 10⁴, 0 ≤ a ≤ 10⁹, 2 ≤ m ≤ 10⁹.
Think about it: Fermat's little theorem only works for a prime modulus. Use the extended Euclidean algorithm instead: it finds x, y with a·x + m·y = gcd(a, m). When the gcd is 1, x (shifted into the range 0 … m−1) is the inverse.
Sample input 1
3 3 11 4 8 10 17
Sample output 1
4 -1 12
Sample input 2
2 1 2 0 5
Sample output 2
1 -1
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).