主题：难题～～难题～～＋分！～
司空怜
[专家分：0] 发布于 2005-11-11 13:41:00
第三题 和不合适
问题描述：
从1、2、3、………、n（n<32768）这n个数中，取出若干个数使其中任意两个数的和都不能被7整除，最多可取多少个数？
输入输出样例：
输入： 输出：
2 2
7 4
100 58
696 399
测试数据是取了所有7的倍数，但任意两个7的倍数相加都能被7整除啊？测试数据是否有问题？
回复列表 （共7个回复）
沙发
mythjoker [专家分：400] 发布于 2005-11-11 17:02:00
我的思路是 从1开始 逐渐加
只要加入的数和前面的分别求和，都不是7的倍数，就加入一个！
不过，我不知道这是不是最优的呢？
板凳
cxxx401 [专家分：140] 发布于 2005-11-12 10:11:00
一定不是!
要知道如果一个数除以7,假设余数是1,那么他与除以7余6的数相加就能被7整除!
也就是说,那么多数中,可以取7的倍数,但只能有一个.
然后是除以7余1的,余2的...取了余1的就不能取余6的...
假设除以7余1的在1..n中有m个,这样去累加.
然后穷举就行了.最后比较那种方法最多.
你明白了么?
3 楼
mythjoker [专家分：400] 发布于 2005-11-12 13:52:00
应该是可以的!
余一的数 一定大于等于 余六的数
4 楼
Benix [专家分：720] 发布于 2005-11-15 17:37:00
楼主给的数据能不能保证一定正确？
5 楼
Benix [专家分：720] 发布于 2005-11-15 17:44:00
我觉得：n=100
令m=trunc(100/7)=14，l=m*7=98
也就是说1~98中，除7余1，除7余2，除7余3... 的数的个数都为14
这么一来，按2楼的说法，可以取余1，余2，余3的数共3*14=42个
还可以取一个能整除7的数，假如是7,就有43个数了
再加上99，100，共45个数啊
可楼主给的是58，是不是我算的过程中有错了
6 楼
小虾虾 [专家分：300] 发布于 2005-11-16 15:04:00
同意
7 楼
chty [专家分：230] 发布于 2005-11-16 16:22:00
测试数据好象有一点问题哦~~~~~~
我来回复
您所在位置：