2023 年北京预赛

解答

记

模 $2$ 时 $F(n)$ 恒为奇数，所以 $2$ 不能整除 $k$。

对奇素数 $p$，因 $P(0)=1$，模 $p$ 有 $F(n)=0$ 当且仅当 $P(X)$ 有一个非零二次剩余根。由欧拉判别法，这又等价于

不是 $1$。把 $X^{(p-1)/2}$ 用重复平方对 $P(X)$ 取余，再作多项式欧几里得算法，得到

对其余不超过 $100$ 的奇素数

同一欧几里得算法均给出 $d_p(X)=1$，故它们都不能整除 $k$。表中每个线性因子的根代入 $P$ 即可核对，第三列再核对该根确为平方。

还需考察不超过 $100$ 的素数幂。对 $p=3,7$ 的上述根，

模 $p$ 均不为零，故由逐级线性提升，每个根唯一提升到所有 $p$ 的幂。所需范围内可取

作为直接核验的根。其他允许素数的平方均大于 $100$。

因此 $k$ 的每个素数幂因子只能来自

反之，对这些两两互素的素数幂任选若干，只要乘积不超过 $100$，中国剩余定理可把各自的根合并成同一个整数 $n$。列出所有可能乘积，得到