论坛 › 编程擂台 › 平方数数字和

无心人 发表于 2008-7-10 08:13:55

我想，做这个题目
用HugeCalc不如单纯的支持
64位整数的C快

另外，暴力搜索到10^16是否合适？？？？

gxqcn 发表于 2008-7-10 08:15:23

赞同楼上观点。:b:

mathe 发表于 2008-7-10 08:16:09

原帖由 gxqcn 于 2008-7-9 10:09 发表 http://bbs.emath.ac.cn/images/common/back.gif
找出一条规律：
　　27…7(n个7)88…8(n+1个8)9 是 16…6(n个6)7 的平方。

该规律虽无法保证得到S(15n+19)的下限，但对缩小下限却很有帮助，
因为除了首位2以外，其它都是相对很大的数字。
这个结论还有一个用处是证明了对于15n+19,存在平方数数字和为这么多。
类似，我们还可以通过166..61,166...62,...,166...69得出类似规律，从而得到另外一些数也存在平方数数字和为这些数字。
不过还不能覆盖所有的自然数。如果能够在找出一些有规律的数，就可能可以证明题目中的猜想。

mathe 发表于 2008-7-10 08:17:15

原帖由 无心人 于 2008-7-10 08:13 发表 http://bbs.emath.ac.cn/images/common/back.gif
我想，做这个题目
用HugeCalc不如单纯的支持
64位整数的C快

另外，暴力搜索到10^16是否合适？？？？
平方数的题目比较合适。素数的题目有难度，这么大范围的素数不好求呀。

无心人 发表于 2008-7-10 08:17:49

:)

或者使用反向递归法从最小可能向上递归
首先固定首位，再考虑末位
末位只能是1，4，5，6，9
而最大位数=(s - 2)
最小位数=(s-10)/9

无心人 发表于 2008-7-10 08:19:40

刚考虑了
每秒最低速度能达到100万
最大速度估计在1000万

无心人 发表于 2008-7-10 08:20:58

或者说
如果编码精细的话

最多一个小时的运算时间
最少可能是10分钟

可惜我一会要出门
呵呵
本来有兴趣作的

gxqcn 发表于 2008-7-10 08:23:13

回复 24# mathe 的帖子

可以通过HugeCalc得到素数（32位下的可分段获取），而后转换成常规类型，
至于统计数字之和，可以分成两部分：
前部分是大于32bit时必须用UINT64，而后的仅用UINT32即可。

要是有64bit的HugeCalc推出就不存在上述问题了。:lol

无心人 发表于 2008-7-10 08:23:24

对小于等于16*9的可以考虑暴力搜索

很大的，就考虑25#的方法吧

kofeffect 发表于 2008-7-10 08:27:50

原帖由 mathe 于 2008-7-10 08:11 发表 http://bbs.emath.ac.cn/images/common/back.gif
C/C++写的代码？要运行多长时间？
C代码（我的代码都不会优化，不好！）
前面的时间还好
要算到下面这个就耗了挺长时间，
n      sum    a(n)
42   64      19999999

下一个不知何时出来，俺关机了:)

查看完整版本: 平方数数字和