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

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封装的每一个高级函数一定都封装了优秀的数学理论。