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

「CodePlus #7」同余方程

题目描述

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


给出若干组正整数 ppxx,求方程 a2+b2x(modp)a^2+b^2\equiv x {\pmod p} 关于 aabb 在模 p\boldsymbol p 意义下解的组数,其中 pp 是奇数,且不包含平方因子。

输入格式

第一行包含一个正整数 nn,表示询问个数。

接下来 nn 行每包含两个用空格分隔的正整数 ppxx,保证 0xp10 \le x \le p - 1pp 是一个奇数,且对任意奇素数 qpq\mid p,都有 q2pq^2 \nmid p

输出格式

输出包含 nn 行,第 ii 行包含一个正整数,表示第 ii 个方程解的组数。

样例

1
5 0
9

99 组解分别为 $(a,b) = (0,0),(1,2),(1,3),(2,1),(2,4),(3,1),(3,4),(4,2),(4,3)$。

数据范围与提示

每个测试点的分值为 55 分。

对于所有数据n105n\le 10^5p107p\le10^7,且 2p2\nmid p\forall 奇素数 qpq2pq\mid p,q^2\nmid p0xp10\le x\le p-1

测试点编号 nn\le pp\le 附加性质
11 55 100100 pp 为奇素数
22 1010 10310^3
33
44 5050 10410^4 pp 为奇素数
55 100100
66 5050
77 100100
88
99 10310^3 10610^6 pp 为奇素数
1010
1111
1212 10510^5 pp 为奇素数
1313
1414
1515
1616
1717 10710^7
1818
1919
2020