您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

约数个数模板

不牌不改 发布时间:2022-03-13 21:31:53 ,浏览量:0

假设 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             
关注
打赏
1662186765
查看更多评论
0.0461s