关于整数的等幂和拆分的计数问题

qianyb

9# wayne


对于我来说，这么大的数通常没什么意义，呵呵

mathe

7# qianyb


一觉醒来，发现将10000表示成20个整数的平方也计算出了，共有257559629384518810765941633263639704组解，比1282051358533580267640长，
wayne 发表于 2010-6-18 16:27

其实只要n不是很大，用动态规划是很快的。
比如将10000表示成20个整数的平方，我们首先需要将100以内所有数据的平方计算出来。
于是我们得到了使用1个整数的平方可以表示的不超过10000的数的集合S1（共100个数）
将S1中每个数再加上S1中另外一个数，如果结果不超过10000,可以得到两个整数的平方和不超过10000的集合S2,（并且可以算出每个元素的计数）然后可以计算S4,S8,S16.在通过S4和S16计算出S20.
其中每趟累加需要O(n^2)的时间，如果k个数字平方和，通常可以通过计算O(log(k))个集合得出最终结果。
当然，上面的方法对于20个整数的排序没有要求。
如果我们要求整数递增排序，那么可以在增加一个参数，比如计算使用了k个整数的平方和，最大整数为h,所能表达的和的集合以及每个元素的计数

hujunhua

10#
可是数论上计数公式不幸地要求因数分解，偶大致知道因数分解目前没有多项式算法。求两个数的最大公约数，数论的公式也是要求因数分解，可是存在绕过因数分解的欧几里德算法。所以我有此疑问，即在这个问题上，你们的不事分解的搜索算法会不会比基于计数公式的算法效率还高。

northwolves

mathe好神奇的速度。
=========================
那个d是函数的一个参数，你可以视为固定的。

比如，第一个方程的解的个数就是  SquaresR[d,n]
将45表示成两个整数的平方和，就是SquaresR[2, 45]=8

将45表示成两个整数的平方和，就是SquaresR[2, 45]=8
包括负整数？

wayne

13# hujunhua
因式分解的效率还是比较不错的。
这里的n一般也就几位数，  远远小于密码学里的几十几百位数的分解那种数量级，

您说的还没有多项式时间的算法，是针对数的位数说话的吧

wayne

14# northwolves
嗯，是的

wayne

12# mathe

大致明白了。

纠正了我对Mathematica一直以来的一个错误认识：以为Mathematica封装的每一个高级函数一定都封装了优秀的数学理论。