找回密码
 欢迎注册
楼主: sw2wolf

[讨论] 高德纳书中一道很普通的题目

[复制链接]
发表于 2010-5-19 10:01:28 | 显示全部楼层
前50个数字只有
1, 2, 3, 5,6,  7,10,  11, 13,14, 15,  17, 19,21, 22,  23,26,  39,30,  31,33,34, 35, 37,38, 39,42,  43,46,  47
情况

评分

参与人数 1威望 +8 鲜花 +8 收起 理由
wayne + 8 + 8

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-19 10:39:03 | 显示全部楼层
这叫 Square Free Integers,不过,你弄掉了一个41

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-19 10:53:49 | 显示全部楼层


我可以证明不存在41这个整数


做梦的时候证明
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-19 13:25:09 | 显示全部楼层
偶的意思是,8, 50等实际上和2是等价类,能不能利用下?
无心人 发表于 2010-5-19 08:47

见32#,44#
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-5-21 13:24:38 | 显示全部楼层
Fans的方法很好,过段时间用c#写一个,看能否1秒之内跑完。
想了一个简单的优化方法,就是先把1,4,9,16,25,36,49排除掉,用fans的方法分为两组,只计算小数部分(当然也可以转为Int64来算),整数部分舍弃。然后根据小数部分算出的结果,再对整数部分DP,应该就可以。
这样的话,空间和时间占用应该都能下降不少。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 16:52 , Processed in 0.050047 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表