SGOI11之《芝麻开门》解题报告
　　　　　　　　　

问题描述
　　对于给定的自然数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