Hide
Problem C
Root of Minus One
Languages
en
is
You are given a prime $p$ satisfying $p = 1 \pmod{4}$ and should find a value $r$ that satisfies $0 \leq r < p$ and $r^2 = -1 \pmod{p}$.
Input
The first and only line of input contains a prime $p \leq 10^{18}$ satisfying $p = 1 \pmod{4}$.
Output
Print a value $r$ satisfying $0 \leq r < p$ and $r^2 = -1 \pmod{p}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
73 |
27 |
