Oh No! You need to sign in or sign up before continuing.
3428 . [模板題] Sqrt Mod
TopCoder
Tags
Description
Each test cases consists of $T$ cases.
Given $Y, P(P: \textrm{prime})$.
Print $X$ s.t. $X^ 2 \equiv Y (\bmod P)$, or $-1$ if there is no such $X$.
Input Format
$T$
$Y_ 0$ $P_ 0$
$Y_ 1$ $P_ 1$
:
$Y_ {T-1}$ $P_ {T-1}$
Output Format
For each line, print $X$ or $-1$.
Sample Input 1
5 0 5 1 5 2 5 3 5 4 5
Sample Output 1
0 1 -1 -1 2
Hints
- $1 \leq T \leq 100,000$
- $2 \leq P \leq 10^ 9$
- $0 \leq Y < P$
- $P$ is prime.
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|