#1 jiangminyang@2010-10-05 06:05:00
17857
回复
删除
没为什么
应为两点间大于100 你总可以通过某种办法跳到所以可以缩
下面是证明
首先证明一个数学定理。如果两个数a,b互质
那么a,b不能构成的最大数小于a*b。
[证明]
要求的这个数可以表示成ax+by=c(即求此时c的最大值)。
问题转化为最小必然能构成的数为多少?
如果c存在,可以得到一个解(x0,y0),ax0+by0=c,方程的通解可以表示成
x=x0+bt y=y0-at
我们需要求正整数解,那么必须满足
x>0,y>0
所以y0/a>t>-x0/b
要保证至少存在一个整数t
所以y0/a+x0/b>=1 所以by0+ax0>=a*b
换句话说,也就是当数是a*b时,必然能构成
所以最大不能构成的数必然小于a*b
[证毕]
因为相领两个数必然互质。
[证明]
假设这两个数不互质,那么他们必然存在一个公因数p
那么一个数为a另一个数为b(a=b+1),那么a=pk b=pk’
所以a-b=pk-pk’=p(k-k’)=1
因为p为整数,所以p=1,所以相邻两个数必然互质。
[证毕]
通过上述两个定理我们可以知道当存在两个数时,不妨记这两个数为a,b那么当步数大于a*b的时候,我们必然可以走到,又因为最大的两个数的乘积小于100 ,所以我们可以把大于100的步长直接缩小为100步,因为大于100步的部分必然能跳到,所以再跳是没有意义的。