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

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

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

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

太厉害了,膜拜!

Avatar_small
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>

Avatar_small
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.

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

Pretty nice post. I have truly enjoyed it.

Avatar_small
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.

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

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

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

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

Avatar_small
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.

Avatar_small
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.

Avatar_small
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.


登录 *


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