题解：P6610 [Code+#7] 同余方程

代数推导保平安。

首先将 $p$ 分解，得到一堆奇质数。根据 CRT，如果在每个数下的解的组数分别为 $t_1,t_2,\cdots$，则最后的答案为 $\prod\limits_i t_i$。

下面只讨论 $p$ 为奇质数的情况（事实上，$p=2$ 也可以用组合意义分讨出来）。出于自己的习惯，将题面中的 $x$ 记为 $r$。

写成式子，答案为：

考虑单位根反演，得到：

整理得：

里面的式子比较碍事，考虑化简。枚举数变成枚举平方，一个数 $t=x^2$ 对应 $1+\left(\dfrac t p\right)$ 个 $x$，因此有：

带回原式得到答案为：

拆开括号：

我们发现 $\sum\limits_{t=0}^{p-1}(\omega_p^i)^t$ 是单位根反演的形式，可以还原成 $p\times[p|i]$。这一项仅在 $i=0$ 时有值，把它单拎出来，得到上式等于：

再根据除了 $0$ 以外，$p$ 的二次剩余与二次非剩余均有 $\dfrac{p-1}2$ 个，得到 $\sum\limits_{t=0}^{p-1}\left(\dfrac t p\right)=0$，因此上式等于：

现在上式满足 $(p,i)=1$，因此 $\left(\dfrac i p\right)^2=1$ 且 $it$ 与 $t$ 共同遍历模 $p$ 完系。因此我们有：

上面用到了勒让德符号的完全积性。带回原式得到答案为：

又有 $\left(\dfrac{i}p\right)^2=1$，得到：

$r=0$ 是否成立会影响第一个括号的值。分两类。当 $r=0$ 时：

否则考虑给第一个括号补上 $i=0$，逆用单位根反演再展开，得到 $r\neq0$ 时的结果：

上面的式子均有共同的一项：$\sum\limits_{t=0}^{p-1}\left(\dfrac{t}p\right)\omega_p^{t}$。问题转化为求该式。

回到一开始的 $\sum\limits_{t=1}^{p-1}\omega_p^{t^2}$，其等于：

去括号：

代入 $\sum\limits_{t=1}^{p-1}\omega_p^{t}=0$，第二个循环提前到从 $0$ 开始，得到：

因此 $\sum\limits_{t=0}^{p-1}\left(\dfrac{t}p\right)\omega_p^{t}=\sum\limits_{t=1}^{p-1}\omega_p^{t^2}$。

等式右边被称为二次高斯和。根据二次互反律证明的相关知识，我们有：