Welcome to Matrix's Garden

World Final 2008 Problem B -- 判断多项式恒被整除

by F.Yang

ACM/ICPC World Final 2008 Problem B 给定整系数多项式 f(x) 及正整数. 判断对取遍所有整数, f(x) 是否恒被整除.

分析我们先定义一些概念.

定义1 设为整系数多项式, 为非零整数, 若对任意 $x \in Z$ , 都有 $d \mid f(x)$ . 我们则称恒被整除.

定义2 记 $f^{(0)}(x) = f(x)$ , $\Delta$ 为向前差分算子, 定义n 阶差分多项式(简称n 阶差分)

$f^{(n)}(x) = \Delta f^{(n-1)}(x) = f^{(n-1)}(x+1) - f^{(n-1)}(x) \,\,\,\,\,\,\, ( n>0 )$ .

我们有如下定理.

定理1 整系数多项式恒被整除, 当且仅当被整除, 且的一阶差分 $f^{(1)}(x)$ 恒被整除.

证明充分性. 因为 f(x) 恒被整除, 所以 $d \mid f(0)$ , $d \mid f(x+1) - f(x) = f^{(1)}(x)$ ( $x \in Z$ ). 充分性得证.

必要性. 使用数学归纳法. $d \mid f(0)$ . 设对非负整数数, 都有 $d \mid f(x)$ . 又因为 $d \mid f^{(1)}(x)$ , 故 $d \mid f(x)+ f^{(1)}(x) = f(x+1)$ . 同理, 设对整数, 有 $d \mid f(x)$ . 则 $d \mid f(x) - f^{(1)}(x-1) = f(x-1)$ . 综合上述, 由数学归纳法知, 必要性得证. $\Box$

定理2 设整系数多项式的次数为 $m= \partial (f(x))$ , 则恒被非零整数整除, 当且仅当 $f(0), f(1), \cdots , f(m)$ 均被整除.

证明充分性是显然的.

必要性的证明施归于纳多项式的次数m. 当 m=0 , 即 f(x) 为常数时, 结论显然成立. 设 $m \leq k$ 时结论成立. 则对 m=k+1 次多项式 f(x) , 若 $f(0), f(1), \cdots , f(k), f(k+1)$ 均被整除, 则 $f^{(1)}(0)=f(1)-f(0)$ , $f^{(1)}(1)=f(2)-f(1)$ , ... , $f^{(1)}(k)=f(k+1)-f(k)$ 均能被整除。又有 $\partial(f^{(1)}(x))<\partial(f(x))=k+1$ . 由归纳假设知, 一阶差分 $f^{(1)}(x)$ 恒被整除. 又根据定理1, 得知 f(x) 恒被整除. 由数学归纳法, 必要性得证. $\Box$