约数之和模板

假设 n n n 可以表示为 n = P 1 α 1 ∗ P 2 α 2 ∗ . . . ∗ P k α k n=P_1^{\alpha_1}*P_2^{\alpha_2}*...*P_k^{\alpha_k} n=P1α1​​∗P2α2​​∗...∗Pkαk​​，其中 P i P_i Pi​ 均为 n n n 的质因子，那么存在结论 n n n 的约数之和为 ( P 1 0 + P 1 1 + . . . + P 1 α 1 ) ∗ ( P 2 0 + P 2 1 + . . . + P 2 α 2 ) ∗ . . . ∗ ( P k 0 + P k 1 + . . . + P k α k ) (P_1^0+P_1^1+...+P_1^{\alpha_1})*(P_2^0+P_2^1+...+P_2^{\alpha_2})*...*(P_k^0+P_k^1+...+P_k^{\alpha_k}) (P10​+P11​+...+P1α1​​)∗(P20​+P21​+...+P2α2​​)∗...∗(Pk0​+Pk1​+...+Pkαk​​)。

大致证明如下：

n n n 的约数可以表示为： ∑ β 1 = 0 α 1 ∑ β 2 = 0 α 2 . . . ∑ β k = 0 α k P 1 β 1 ∗ P 2 β 2 ∗ . . . ∗ P k β k \sum_{\beta_1=0}^{\alpha_1}\sum_{\beta_2=0}^{\alpha_2}...\sum_{\beta_k = 0}^{\alpha_k}P_1^{\beta_1}*P_2^{\beta_2}*...*P_k^{\beta_k} ∑β1​=0α1​​∑β2​=0α2​​...∑βk​=0αk​​P1β1​​∗P2β2​​∗...∗Pkβk​​。

对这个式子进行因式分解得到结论不容易，但是将结论的括号拆开得到求和的形式还是比较容易的。

从结论的第一个括号选一项、第二个括号选一项、……、最后一个括号选一项，相乘构成新的一项，这样得到的每一项再相加，正是求和的形式。

问题转化为了分解质因数。

#include
using namespace std;

int main()
{
	int n, ans = 1;
	cin >> n;
	
	for (int i = 2;i * i  1) ans *= (n + 1);
	cout