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大学生程序设计竞赛训练》暑期课面向全球招生!

我有个证明,大家可以讨论一下。。

Posted by cug_fish2008 at 2010-05-10 10:54:59 on Problem 1091
假设n个数为x1,x2,...xn。
那么就是求|t1*x1+t2*x2+...+tn*xn+t*M|=1;(t1,t2..tn分别为任意整数)
如果gcd(x1,x2,..xn,M) =w;(w>1)
则x1 = q1*w,x1=q2*w,...xn=qn*w,M=q*w.替换后
|t1*q1*w+t2*q2*w+....+tn*qn*w+t*q*w|=1。
由于t1,t2,...tn,t为任意整数,则t1*q1,t2*q2,...tn*qn,t*q也为任意整数。

所以可以改写成==>|t1*w+t2*w+...+tn*w+t*w|=1。(t1,t2..tn分别为任意整数)
显然不成立,因为w>1,结果肯定为w的倍数。

那如果w=1,那么可以知道肯定存在一组整数t1,t2,...tn,t使得上式成立。

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