申强也来解那道清华金秋营题

题目是：给定奇质数p和整数a，求x^2+y^2≡a(modp)的同余解的个数。

我们可以看作传球问题，每次“传球”的动作是加一个平方数。

则其转移矩阵（记为M）满足a(i,j)=

1，i=j；2，i-j为模p的二次剩余；0，i-j为模p的非二次剩余。

我们需要计算M^2。

该矩阵为循环矩阵，因此循环等比数列（公比为p次单位根的p项等比数列）均为其特征向量，它们对应的特征值是p（一重），以及±(-1)^((p-1)/4)*√p（各为(p-1)/2重）。）

M^2也为循环矩阵，且其特征值为M的特征值的平方：p^2（一重），以及(-1)^((p-1)/2)*p（p-1重）。

易知，一个由实数组成的循环矩阵若有p-1个特征根相等，则除主对角线以外的所有元素相等。记主对角线上的元素为s，其他元素为t，则有：

s+(p-1)t=p^2

s-t=(-1)^((p-1)/2)*p

因此，s=p+(-1)^((p-1)/2)*(p-1)，t=p-(-1)^((p-1)/2)。

s对应a为p的倍数时的方法数，t对应a不为p的倍数时的方法数。