假设 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αkP1β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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?