约数之和（数论）

2024-01-27 11:03| 来源: 网络整理| 查看: 265

前言

失恋了跑过来写这题，想当年这题咕了好久，现在分分钟切了。

ACwing题目地址

Solution

通过唯一分解定理：

\[A=p^{\alpha_1}_1*p^{\alpha_2}_2*...*p^{\alpha_n}_n \]

所以：

\[A^B=p^{\alpha_1*B}_1*p^{\alpha_2*B}_2*...*p^{\alpha_n*B}_n \]

通过自己研究研究可以知道的两个定理：

1.约数个数定理：

\[Num(A)=(1+\alpha_1)*(1+\alpha_2)*...*(1+\alpha_n) \]

解释：从每一个质数里面任选一个次幂（选择范围 \([0,\alpha_i]\)），与其他质数相组合就是一个约数，所以约数个数就是上面这个式子。

2.约数和定理：

\[Sum(A)=(1+p_1^1+p_1^2+...+p_1^{\alpha_1})*(1+p_2^1+p_2^2+...+p_2^{\alpha_2})*...*(1+p_n^1+p_n^2+...+p_n^{\alpha_n}) \]

解释：每个括号里面就是每一个质数的任一个次幂（次幂范围 \([0,\alpha_i]\)）之和，如果把括号拆开，就是每个括号里面选一个数乘起来，再把所有选择加起来。每个括号选一个数乘起来，不正对应每一个约数的值吗？所以约数和就是上面这个式子。

上面这个式子有亿点点难看，我们把它写简洁一点就是：

\[Sum(A)=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i}p_i^j) \]

回到题目，在这个题目里的约数和就是如下式子：

\[Ans=\prod_{i=1}^n (\sum_{j=0}^{\alpha_i*B}p_i^j) \]

暴力计算复杂度 \(O(n^2)\)，还要带上个质因数分解的复杂度。本题数据 \(n

【本文地址】

公司简介

联系我们

约数之和 （数论）