高德纳书中一道很普通的题目

无心人

前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 情况

wayne

这叫 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

无心人

我可以证明不存在41这个整数 做梦的时候证明

shshsh_0510

偶的意思是，8， 50等实际上和2是等价类，能不能利用下？ 无心人 发表于 2010-5-19 08:47

见32#，44#

litaoye

Fans的方法很好，过段时间用c#写一个，看能否1秒之内跑完。 想了一个简单的优化方法，就是先把1,4,9,16,25,36,49排除掉，用fans的方法分为两组，只计算小数部分（当然也可以转为Int64来算），整数部分舍弃。然后根据小数部分算出的结果，再对整数部分DP，应该就可以。 这样的话，空间和时间占用应该都能下降不少。