Square Root Modulo a Prime
Find any x with x² ≡ A (mod P) for prime P, or print −1 if A is not a quadratic residue. Print the smaller of the two roots.
Input: one line with two integers A and P.
Output: the smaller square root, or −1.
Constraints:
- 2 ≤ P ≤ 109, P prime
- 0 ≤ A < P
Sample Tests
Input 1
2 7
Output 1
3
Input 2
3 7
Output 2
-1
Discussion (opens after you solve — no spoilers before)
No comments yet.