[Code+#7] 同余方程
题目描述
这就是一些朴素的二次同余方程:)
------------------
给出若干组正整数 $p$ 和 $x$,求方程 $a^2+b^2\equiv x {\pmod p}$ 关于 $a$ 和 $b$ **在模 $\boldsymbol p$ 意义下**解的组数,其中 $p$ 是奇数,且不包含平方因子。
输入输出格式
输入格式
第一行包含一个正整数 $n$,表示询问个数。
接下来 $n$ 行每包含两个用空格分隔的正整数 $p$ 和 $x$,保证 $0 \le x \le p - 1$,$p$ 是一个奇数,且对任意奇素数 $q\mid p$,都有 $q^2 \nmid p$。
输出格式
输出包含 $n$ 行,第 $i$ 行包含一个正整数,表示第 $i$ 个方程解的组数。
输入输出样例
输入样例 #1
1
5 0
输出样例 #1
9
说明
### 样例解释
$9$ 组解分别为 $(a,b) = (0,0),(1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3)$。
### 子任务
每个测试点的分值为 $5$ 分。
**对于所有数据**,$n\le 10^5$,$p\le10^7$,且 $2\nmid p$,$\forall$ 奇素数 $q\mid p,q^2\nmid p$,$0\le x\le p-1$。
| 测试点编号 | $n\le$ | $p\le$ | 附加性质 |
| :--------: | :----: | :----: | :------------: |
| $1$ | $5$ | $100$ | $p$ 为奇素数 |
| $2$ | $10$ | $10^3$ | $p$ 为奇素数 |
| $3$ | $10$ | $10^3$ | |
| $4$ | $50$ | $10^4$ | $p$ 为奇素数 |
| $5$ | $100$ | $10^4$ | $p$ 为奇素数 |
| $6$ | $50$ | $10^4$ | |
| $7$ | $100$ | $10^4$ | |
| $8$ | $100$ | $10^4$ | |
| $9$ | $10^3$ | $10^6$ | $p$ 为奇素数 |
| $10$ | $10^3$ | $10^6$ | |
| $11$ | $10^3$ | $10^6$ | |
| $12$ | $10^5$ | $10^6$ | $p$ 为奇素数 |
| $13$ | $10^5$ | $10^6$ | |
| $14$ | $10^5$ | $10^6$ | |
| $15$ | $10^5$ | $10^6$ | |
| $16$ | $10^5$ | $10^6$ | |
| $17$ | $10^5$ | $10^7$ | |
| $18$ | $10^5$ | $10^7$ | |
| $19$ | $10^5$ | $10^7$ | |
| $20$ | $10^5$ | $10^7$ | |