Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:该题的推广与证明

Posted by 2641145181 at 2018-08-01 09:07:07 on Problem 1091
In Reply To:该题的推广与证明 Posted by:SiaoD at 2010-05-31 11:21:48
> 	设有n个自然数,分别为a1, a2, a3 ....an,设其最大公约数为d, 则对于任意整数k1, k2, k3....kn(其最大公约数为e),可以得出c = k1*a1 + k2 * a2 + k3 * a3 ...kn * an的最小自然数为d*e。
> 	下面只证明k1, k2, ...kn最大公约数为1和a1, a2, ....an最大公约数为1的情况。如果该情况得证,其它情况通过提取最大公约数可以转化为该情况。
> 	首先证明n=2时候的情况,即c = k1*a1 + k2*a2的情况:
> 	设a2 > a1且 a2 / a1 = p 余q,有:
> 	c = k1*a1 + k2*a2                                  1		
> 	c = k1 * a1 + k2 * (p*a1 + q)                      2
> 	c = (k1+k2*p) *a1 + k2 * q                         3
> 	c = k1' * a1 + k2 * q                              4
> 	k1' 与k2的最大公约数依然为1, 而通过1式到4式的转换可以看出可以把较大的一个因数转化为该因数与另外一个因数的模,即上式中的把a2转化为q。
> 	而我们都知道,这样不断模的结果就是a1和a2的最大公约数,所以c可以最后转化为:
> 	c = k1'' * 1 + k2'' * 1
> 	得证。
> 	对于n = 3个的情况,即c= k1 * a1 + k2 * a2 + k3 * a3的情况,设a1, a2 的最大公约数为z, 则z 与a3的最大公约数必为1.
> 	前两个提取z后,可以转化为n = 2时假的情况,故得证。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator