P6610 [Code+#7] 同余方程
首先可以中国剩余定理。
至于为什么 \(a,b\) 在满足同余条件后 \(a^2+b^2\) 仍然满足，是因为根据中国剩余定理的过程，会得到只有当前方程结果为 \(a\) 的数加起来，所以不管套什么函数都是对的。
然后就是推式子了。
\[\begin{aligned} ans&=\sum_{a+b\equiv x}\left(\left(\dfrac{a}{p}\right)+1\right)\left(\left(\dfrac{b}{p}\right)+1\right)\\ &=p+\sum_{0\le a<p}\left(\dfrac{a(x-a)}{p}\right)+2\left(\dfrac{a}{p}\right)\\ &=p+\sum_{0\le a<p}\left(\dfrac{\frac{x}{a}-1}{p}\right)\\ \end{aligned} \]然后直接算即可。
标签：+#,P6610,Code,right,left,同余 From： https://www.cnblogs.com/One-coder/p/18184197