假设 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 的约数的个数为 ( α 1 + 1 ) ∗ ( α 2 + 1 ) ∗ . . . ∗ ( α k + 1 ) (\alpha_1+1)*(\alpha_2+1)*...*(\alpha_k+1) (α1+1)∗(α2+1)∗...∗(αk+1)。
大致证明如下:由于每一个数均可由某些质数的若干次幂的乘积构成,且不同质数的不同次幂会构成不同的数,即一一对应关系,因此对于 m = P 1 β 1 ∗ P 2 β 2 ∗ . . . ∗ P k β k m=P_1^{\beta_1}*P_2^{\beta_2}*...*P_k^{\beta_k} m=P1β1∗P2β2∗...∗Pkβk, 0 ≤ β i ≤ α i 0≤\beta_i≤\alpha_i 0≤βi≤αi,即 β i \beta_i βi 存在 α i + 1 \alpha_i+1 αi+1 种选择,所以构成数的总个数为 ( α 1 + 1 ) ∗ ( α 2 + 1 ) ∗ . . . ∗ ( α k + 1 ) (\alpha_1+1)*(\alpha_2+1)*...*(\alpha_k+1) (α1+1)∗(α2+1)∗...∗(αk+1)。又因为 m m m 必然整除 n n n,所以 ( α 1 + 1 ) ∗ ( α 2 + 1 ) ∗ . . . ∗ ( α k + 1 ) (\alpha_1+1)*(\alpha_2+1)*...*(\alpha_k+1) (α1+1)∗(α2+1)∗...∗(αk+1) 即为 n n n 的约数个数。
问题转化为了分解质因数。
#include
using namespace std;
int main()
{
int n, ans = 1;
cin >> n;
for (int i = 2;i * i 1) ans *= 2;
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脚手架写一个简单的页面?