算法 1：暴力
直接枚举 a 和 b 得到结果。
15 分。
算法 2：利用二次剩余
因为这是一个二次同余方程，我们就可以用二次剩余来完成。
具体地说，我们可以建立一个 quad 数组
时间复杂度 O(np)，可得 40 分。
算法 3：充分利用二次剩余
现在我们需要将 p 为质数的情况完美地解决。
事实上如果对小质数尝试打表的话，会发现如下规律。
当 pmod4=1,x=0 时，解的个数为 2p−1。
当 pmod4=1,x
=0 时，解的个数为 p−1。
当 pmod4=3,x=0 时，解的个数为 1。
当 pmod4=3,x
=0 时，解的个数为 p+1。
上述结论也是可以严谨证明的，请感兴趣的同学尝试证一下。
于是在 p 为质数的情况下，可以 O(n) 完成，可得特殊情况的 30 分。
算法 4：中国剩余定理+算法 3
我们在算法 3 中已经完美地解决了 p 为质数的情况，我们现在将其拓宽捣任意的情况。
注意到题目中限制了 p 中没有平方因子，所以对 p 进行质因数分解
我们设 xmodp
i
=x
i
那么原本的方程化为了 k 个同余方程 a
互不相等，所以这 k 个方程互相独立。而且有中国剩余定理可以证明，原方程的解与这个方程的解一一对应。
具体来说，如果 (a,b) 为原方程的一组解，那么 (amodp
i
,bmodp
i
) 为地 i 个方程的一组解。
反之，如果我们对第 i 个方程找到了一组解 (a
i
,b
i
)，那么存在唯一的一对 (a,b) 使得 amodp
i
=a
i
,bmodp
i
=b
i
，它是方程的一组解。
由此，我们可以对每一个方程去求解的个数，最后将他们相乘，得到最后的答案。
时间复杂度主要受质因数分解限制，若直接枚举，时间复杂度为 O(n
p
)。
若先用欧拉筛筛出质数表，则可将时间复杂度优化为 O(p+nπ(
p
))。
代码
#include <cstdio>
#define int long long
int n, p, x, result[10];
void Break(int);
signed main()
{
scanf("%lld", &n);
while(n--)
{
int ans = 1;
scanf("%lld%lld", &p, &x);
Break(p);
for (int i = 1; i <= result[0]; i++)//枚举每一个方程
{
int xx = x % result[i];
if (result[i] % 4 == 1)
{
if (!xx)
ans *= 2 * result[i] - 1;
else
ans *= result[i] - 1;
}
if (result[i] % 4 == 3)
{
if (!xx)
ans *= 1;
else
ans *= result[i] + 1;
}
}
printf("%lld\n", ans);
}
return 0;
}
void Break(int n)//质因数分解
{
result[0] = 0;
for (int i = 2; i * i <= n; i++)if (n % i == 0)
{
n /= i;
result[++result[0]] = i;
}
if (n)
result[++result[0]] = n;
}
