原文链接：http://www.mydrs.org/program/list.asp?id=357
问题描述对于给定的自然数n和k（1≤n＜
，1≤k＜20），求
的所有正整数因子的和。分析
（1） 任意大于等于2的正整数都可以被分解质因数，
则n可以表示成为：
可以表示成为： 
其中，
为素数，
,且
为任意正整数（2） 正整数n的任意约数都可以用n的质因数的积的形式表示。
例如：n=6时，n的约数有1，2，3，6。
其中：
解法
（1）由上面的分析，我们很容易想到递归搜索的解法，依次递归决定各质因数使用次数，构造出
的约数，并累加求出总和。由于的约数个数较大，所以程序运行速度很慢，不能再时限内出解。（2）我们观察搜索树就能发现，确定了前面的质因子的使用次数，后面的搜索完全一样，我们便可以用记忆化搜索减少重复搜索，速度大大提高。
（3）由此，我们很容易的找到了求
所有约数之和的公式： 
（4）在此基础上，我们利用等比数列的求和公式，可以改进公式为：
小结
本题考察了对约数的理解，并在解题中运用了高精度运算。
附：源程序参见 ah02t4.pas
作者：
来源：ChinaSchool
时间：2002-05-03
上一篇：SGOI11之《黑白图像压缩》
下一篇：SGOI-12友谊赛测试数据