也是 luogu#6610 的题解。

感谢数竞同学的做法

数竞同学真是太强了！

---

简述一下题意，给定 ，求满足同余方程 的解的组数，其中 且 。

只需要考虑 为奇质数时的情况，这是因为显然 的答案就是分别考虑 情况下答案的数量之积。

容易发现如下等式成立：，所以所求即 . 不妨先考虑如何求 。以下讨论均建立在 基础下，有些步骤不再写出。

三项式定理展开一下：

考察式子 , 不妨设 的一个原根为 ，由 知 a 遍历 ，所以原式即 ，除非 时原式等于 ，否则原式等于 0。而又 ，故只有 时 不为 0。

所以 ，又有：

所以 。

所以 。

接下来对 进行一些讨论。若 不等于 ，我断言答案组数为偶数且不大于 。可以分 是否是二次剩余讨论证明，留给读者思考。所以若 则答案为 。若 ，首先有解 ，且其它解均成对出现，故答案为奇数。所以当 时答案为 1，否则答案为 。