CII2187-一般任务安排问题的最小费用最大流解法及其他
Google Code Jam Round1A "Number"

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

Matrix posted @ 2008年7月27日 04:34 in Problem Analysis with tags 多项式 整除 差分 , 1836 阅读

by F.Yang   

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

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

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

      定义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(x) 恒被d整除, 当且仅当f(0)d 整除, 且f(x) 的一阶差分f^{(1)}(x)恒被d 整除.

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

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

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

      证明  充分性是显然的.

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

      定理3  设整系数多项式f(x)的次数为m= \partial (f(x)), 则f(x)恒被非零整数d整除, 当且仅当对任意连续m+1个整数x_0,  x_0+1,  \cdots,  x_0+m, 有f(x_0), f(x_0+1), \cdots, f(x_0+m)均被d整除.

      定理3作为定理2的推广, 证明方法也是类似的, 此处从略.

      推论1  设整系数多项式f(x)的次数为m= \partial (f(x)), g=(f(0), f(1), \cdots, f(m)), f(x)恒被d整除当且仅当d \mid g.

      至此,整个问题得到完整解决.   

Avatar_small
小伟 说:
2008年7月27日 12:05

太厉害了,膜拜!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter