2013第12届CGMO试题

• 知识点

  >

  二试数论部分

略

易知素因数分解 $2013=3\times 11\times 61$．记 $p_1 =3,p_2 =11,p_3 =61$，对 $a,b\in\{1,2,\ldots,2013\}$，设 $a$ 除以 $p_i$ 的余数是 $a_i$，$b$ 除以 $p_i$ 的余数是 $b_i$（$i=1,2,3$）．由中国剩余定理，$(a,b)$ 与 $(a_1 ,a_2 ,a_3 ,b_1 ,b_2 ,b_3 )$ 一一对应．
令 $f_i (x)=ax^3 +bx$，$i=1,2,3$．我们称满足 $f(0),f(1),\ldots,f(n-1)$ 除以 $n$ 的余数互不相同的多项式为"模 $n$ 的好多项式"．
若 $f(x)=ax^3 +bx$ 不是模 $2013$ 的好多项式，则存在 $x_1 \not\equiv x_2 \pmod{2013}$ 使 $f(x_1 )=f(x_2 )\pmod{2013}$．设 $x_1 \not\equiv x_2 \pmod{p_i}$，取 $u_1 ,u_2$ 分别是 $x_1 ,x_2$ 除以 $p_i$ 的余数，则 $u_1 \not\equiv u_2 \pmod{p_i}$ 且 $f_i (u_1 )\equiv f_i (u_2 )\pmod{p_i}$．故 $f_i (x)$ 不是模 $p_i$ 的好多项式．
若 $f(x)=ax^3 +bx$ 是模 $2013$ 的好多项式，则每个 $f_i (x)$ 是模 $p_i$ 的好多项式，理由如下：
对任意不同的 $r_1 , r_2 \in \{ 0,1,\ldots,p_i -1\}$，存在 $x_1 , x_2 \in \{1,2,\ldots,2013\}$ 使得
$
x_{1} \equiv x_{2}\left(\bmod \frac{2013}{p_{i}}\right) \text{ 且 } x_{1} \equiv r_{1}, x_{2} \equiv r_{2}\left(\bmod p_{i}\right)
$
因为 $f(x_1 )\not\equiv f(x_2 )\pmod{2013}$，而 $f(x_1 )\equiv f(x_2 )\pmod{2013}$，所以 $f(r_1 )\not\equiv f(r_2 ) \pmod{p_i}$，结论成立．
因此，我们的问题转化为求模 $p_i$ 的好多项式 $f_i (x)$ 的个数．
对于 $p_1=3$，由费马小定理，
$
f_{1}(x) \equiv a_{1} x+b_{1} x \equiv\left(a_{1}+b_{1}\right) x(\bmod 3)
$
是好多项式等价于 $a_1 +b_1$ 不是 $3$ 的倍数，这样的 $f_i (x)$ 共有 $6$ 个．
对 $i=2,3$，若 $f_i (x)$ 是模 $p_i$ 好多项式，则对任意 $u$ 和 $v\not\equiv 0\pmod{p_i}$，$f_i (u+v)\not\equiv f_i (u-v)\pmod{p_i}$，即 $p_i$ 不整除
$
f_{i}(u+v)-f_{i}(u-v)=2 v\left[a_{i}\left(3 u^{2}+v^{2}\right)+b_{i}\right]
$
若 $a_i \neq 0$，集合
$
A=\left\{3 a_{i} u^{2} | u=0,1, \cdots, \frac{p_{i}-1}{2}\right\}
$
与
$
B=\left\{\left(-b_{i}-a_{i} v^{2}\right) | v=1,2, \cdots, \frac{p_{i}-1}{2}\right\}
$
中的数模 $p_i$ 的余数不重叠．显然 $A,B$ 内部的数模 $p_i$ 互不同余，
并且 $|A|+|B|=p_i$，这样 $A\cup B$ 的 $p_i$ 个元素的余数是 $0,1,\ldots,p_i -1$ 的排列，因而它们的和是 $p_i$ 的倍数，即
$\displaystyle
\sum\limits_{u=0}^{\frac{p_i -1}{2}} 3 a_{i} u^{2}+\sum_{v=1}^{\frac{p_i -1}{2}}\left(-b_{i}-a_{i} v^{2}\right) \equiv 0\left(\bmod p_{i}\right)
$．
$1^{2}+2^{2}+\dots+\left(\frac{p_{i}-1}{2}\right)^{2}=\frac{1}{6} \cdot \frac{p_{i}-1}{2} \cdot \frac{p_{i}+1}{2} \cdot p_{i}$ 是 $p_i$ 的倍数，导致 $-\frac{p_i -1}{2}\cdot b_i$ 也是 $p_i$ 的倍数，这样 $b_i$ 是 $p_i$ 的倍数，即 $a_i,b_i$ 中至少有一个是 $0$，并且显然不能同时为 $0$．
若 $a_i =0, b_i \neq 0$，则 $f_i (x)=b_i x$ 显然是好多项式．这样的好多项式有 $p_i -1$ 个．
若 $a_i \neq 0,b_i =0$，则 $f_i (x)=a_i x^3$．
对 $p_2 =11$，由费马小定理 $(x^3 )^7 =x^{21} \equiv x \pmod{11}$，
故对于 $x_1 \neq x_2 \pmod{11}$，$x_{1}^{3}\neq x_{2}^{3} \pmod{11}$，
$f_2 (x)=a_2 x^3$ 是好多项式．这样的共有 $10$ 个．
对 $p_3=61$，由于 $4^3 =64\equiv 125=5^3 \pmod{61}$，
所以 $f_3 (x)=a_3 x^3$ 不是好多项式．
所以，总的个数是 $6\times (10+10)\times 60=7200$．