Hide
Problem D
All Modulo Pythagorean
Languages
en
is
You are given a value $n$ and should investigate Pythagorean triples modulo $n$. This means we are considering triples $(a, b, c)$ where $0 < a, b, c < n$ that satisfy $a^2 + b^2 = c^2 \pmod{n}$ and $a \leq b$.
For example in the first sample the solutions are $(1, 2, 1)$, $(1, 2, 3)$, $(2, 2, 2)$, $(2, 3, 1)$ and $(2, 3, 3)$.
Input
The first and only line of input contains a positive integer $n$, the modulo we are considering. It will satisfy $1 \leq n \leq 2 \cdot 10^5$.
Output
Print the number of Pythagorean triples modulo $n$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 |
5 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 |
18 |
| Sample Input 3 | Sample Output 3 |
|---|---|
15 |
64 |
