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

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

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$

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

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

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

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

[回复]

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

太厉害了，膜拜！

[回复]

izzy games 说:
2021年9月09日 22:52

This is a great inspiring article.I am pretty much pleased with your good work.You put really very helpful information. Keep it up. Keep blogging. Looking to reading your next post.<a href="https://gizzygames.net/">https://gizzygames.net/</a>

[回复]

Macys Credit Card Lo 说:
2022年8月27日 22:43

Macy's Credit Card. Want to pay your bill online? Sign in to access your account and make a one-time payment, Macys Credit Card Login or set up monthly auto-payments for hassle-free. Explore Entertainment Access ... If your Macy's Credit Card Account is closed by you or us, or you fail to make a qualifying purchase on your Macy's Credit Card 2021.

[回复]

rehabilitation cente 说:
2022年8月29日 22:48

Pretty nice post. I have truly enjoyed it.

[回复]

GSEB STD-1 Question 说:
2022年9月10日 22:09

Gujarat State Department of School Education, Gandhinagar and the State level subject experts and other private school teaching staff of the Elementary Level Primary School have designed and suggested the GSEB 1st Class Model Paper 2023 with sample answers Set wide as SET-A, SET-B, SET-C and SET-D to know the new exam scheme or question pattern. GSEB STD-1 Question Paper Students of the Gujarat state can download the NCERT & SCERT Syllabus GSEB STD-1 Question Paper 2023 Pdf with sample answers along with the class teacher’s suggested all lesson or chapter’s most important questions for Part-A, Part-B, Part-C and Part-D exams of Term-1 & Term-2 to the academic year of 2023.

[回复]

Anonymous 说:
2023年1月29日 20:48

This is very interesting, but it is necessary to click on this link: 룸알바

[回复]

Anonymous 说:
2023年2月06日 14:47

It's superior, however , check out material at the street address. 슈어맨

[回复]

san diego web design 说:
2023年3月02日 21:07

custom web design company is an important face of your brand. It is your identity and your business is recognized by it. Your logo is a seal that traces your impression in the hearts and minds of your customers. We provide complete web design services for small business. Our development team and designers are exceptionally creative with vast experience in top-notch business industries in san Diego web design firm.

[回复]

www.questionspapers 说:
2023年7月05日 10:33

Professional writers have joined forces to launch the questionspapers project, which provides in-depth news coverage of current events across the nation.Our team is made up of professional writers and citizen www.questionspapers.in journalists with a wide range of journalism interests who are committed about delivering education updates in the public interest while maintaining transparency.Our reporting team plans to release the Education & Recruitment Update for all age groups and provide inside coverage to show the real picture of current occurrences.

[回复]

BSEB Inter Question 说:
2023年7月14日 18:45

BSEB Inter Question Paper 2024 BSEB Conduct Examinations for both Hindi, English Medium Senior Secondary Standards, BSEB will hold the Intermediate Public Exam From Start Month of February, 2024, Bihar Board Science, Commerce, and Arts Examination Started from 09:30 AM to Scheduled Time which Lasted Till 12:45 PM, Here we will tell you about the Bihar Board Question Paper 2024 for intermediate, in which BSEB Inter Question Paper 2024 we will give you complete information about the Reduced Exam Pattern, According to the Reports, Every year, more Than 7 to 8 lakh Students Appear for the Intermediate Examination 2024. We Provide Bihar Model Paper 2024 for Intermediate the Subjects of Science, Commerce, and Arts. to view or Download the Bihar Board 12th Model Paper 2024 and its Solutions, Students need to visit our website Regular Available More Details, Here we are Providing the Complete Information of Science, Commerce & Arts to the Students, the Examination of that Question Paper was given by the Students of Intermediate, That is, the code for this Bihar Board 12th Question Paper 2024.

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

Matrix

分类

最新评论

最新留言

友情链接

功能

浏览计数器