#6724. 「CodePlus #7」同余方程

内存限制:512 MiB 时间限制:1100 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

这就是一些朴素的二次同余方程:)


给出若干组正整数 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

样例解释 1

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
3
4 50 10^4 p 为奇素数
5 100
6 50
7 100
8
9 10^3 10^6 p 为奇素数
10
11
12 10^5 p 为奇素数
13
14
15
16
17 10^7
18
19
20