魔方吧·中文魔方俱乐部

标题: 谁来帮我理一下思路，我老了吗？ [打印本页]

作者: Get_FBlood 时间: 2009-9-26 20:50:08 标题: 谁来帮我理一下思路，我老了吗？

问题是这样的，N个人围成一圈，有一个人手上有一个球，将顺时钟传递，每次传K个人（1<=k<n/2)
求K的最大值，使当球再次传到第一个人手上的时候，所有的人都拿到过球？

思路：要再次传到第一个人的手上，就必须传了整数个圈，设为X圈，要是没个人都拿过球，
刚传了N下，刚X*N=K*N，也就是要传K圈，这意味着什么？接着是怎样做呢？

作者: zxl0714 时间: 2009-9-26 21:21:15

首先传完一轮要正好N次。如果在这N次中球没有回到第一个人的手上，那么一定所有人都拿过球。由此可知i * K不能整除N（ 1 <= i < N ），所以K和N的最小公倍数就是K * N，由此可见K与N互质，接下来就找一个与N / 2最接近的并且和N互质的数就行了。

作者: dfst258 时间: 2009-9-26 21:21:52

内容看不懂，看来我也老了。不仅没有思路，连内容什么意思都没看懂~

作者: aben306 时间: 2009-9-26 22:08:10

呵呵....有些难度哦....思考一下吧...

作者: lj040051 时间: 2009-9-26 22:32:03

怎么老来这种题啊～～～～～～～～～～～

作者: Get_FBlood 时间: 2009-9-27 17:59:51

高人啊，
一语点醒梦中人啊

作者: oboe 时间: 2009-9-29 17:35:58

想到循环小数去了...
2楼正解吗？
N个人，如果N次中有重复，必定包括了第一人。
N次中不重复，必定传遍了所有人。

后面的最大的K还没想明白
如果 1<K<N, 则K=n-1，就是一个逆序的传递.

作者: oboe 时间: 2009-9-29 22:54:20

仍然不考虑 1<K<N/2,
有二个解
K=n-1，就是一个逆序的传递.
K=n+1, 一个正序的传递。
狠明显，K能因式分解的话，公因数都是正解。
再考虑题目要求1<=k<n/2
所以在n<2以下的公因数就可以。

另外要证明 K=n-1 或者 K=n+1是唯一解，
假设K=n-2有解，则因为 n-2到n-1的关系符合 n和n+1，可以归入K=n+1类，与题目要求不符合，所以假设K=n-2是错的。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)