约数个数模板

假设 $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$ 的约数的个数为 ( α 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$ 必然整除 $n$，所以 ( α 1 + 1 ) ∗ ( α 2 + 1 ) ∗ . . . ∗ ( α k + 1 ) (\alpha_1+1)*(\alpha_2+1)*...*(\alpha_k+1) (α1​+1)∗(α2​+1)∗...∗(αk​+1) 即为 $n$ 的约数个数。

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

#include
using namespace std;int main()
{int n, ans = 1;cin >> n;for (int i = 2;i * i <= n;i ++) {if (n % i == 0) {int cnt = 1;while (n % i == 0) n /= i, cnt ++;ans *= cnt;}}if (n > 1) ans *= 2;cout << ans << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！