约数个数模板

假设 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