整数因子分解问题(递归分治法、动态规划)

Description

大于1的正整数n可以分解为：n=x₁ * x₂ * … * x_m。例如，当n=12 时，共有8 种不同的分解式： 12=12； 12=6 * 2； 12=4 * 3； 12=3 * 4； 12=3 * 2 * 2； 12=2 * 6； 12=2 * 3 * 2； 12=2 * 2 * 3。对于给定的正整数n，计算n共有多少种不同的分解式。

Input

输入数据只有一行，有1个正整数n (1≤n≤2000000000)。

Output

将计算出的不同的分解式数输出。

Sample Input

Sample Output

下面是AC代码:

递归法:

耗时有些大，但是通过了。

$f(n)$ 为n的不同分解式个数。

$f(n) = sum_{n\%i==0} f(n/i),\ 2 <= i <= n$

比如20

$f(1) = 1$

$f(20) = f(2) + f(10) + f(4) + f(5) + f(1)$

$f(2) = f(1) = 1$

$f(10) = f(2) + f(5) + f(1) = 1 + 1 + 1 = 3$

$f(4) = f(2) + f(1) = 1 + 1 = 2$

$f(5) = f(1) = 1$

所以：$f(20) = 1 + 3 + 2 + 1 + 1 = 8$

发现$f(n)里会有f(n/n)$，所以$f(n)$初始值可以初始化为1

for循环找因子也不用一直到n，到sqrt(n)就行，也就是i * i < n就行

最后判断一下i * i == n，因为左右因子都一样怎么交换都一样，所以只用加上$f(i)$即可

比如$f(100) = f(2) + f(50) + f(4) + f(25) + f(5) + f(20) + f(10) + f(1)$

i * i < n，$f(n) = sum_{n \% i == 0} (f(n / i) + f(i))$

i * i == n，$f(n) = f(n) + f(i)$

比如$f(20) = f(2) + f(10) + f(4) + f(5) + f(1)$

找出$f(2)$就可以加上$f(20 / 2) = f(10)$，$f(4)$可以得$f(20/4) = f(5)$

// 递归法
#include <stdio.h>

int solve(int n)
{
	int ans = 1, i;					// ans = 1初始表示n = n的情况
	for (i = 2; i * i < n; i++)		// 因子乘因子小于n
		if (n % i == 0)				// i 是 n的因子, n / i也是n的因子
			ans += solve(i) + solve(n / i);
	if (i * i == n)					// i是n的因子, 并且i * i == n时只有这一种情况, 左右交换也是一种
		ans += solve(i);
	return ans;
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d
", solve(n));
	return 0;
}

动态规划法：

算术基本定理：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

$$ N = p_1^{x_1} * p_2^{x_2} * ...*p_n^{x_n} \ p_1, p_2, ... ,p_n都为质数 \ x_1, x_2, ... ,x_n都是大于等于0的整数 $$

可以得出：

N正因子个数为$(x_1 + 1) * (x_2 + 1) * ... * (x_n + 1)$

2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230

6469693230的正因子个数为：2¹⁰ = 1024 , 所以存因子的数组开2000就差不多了

dp[i]存的是factor[i]的分解式个数

一个数可以分解为因子乘积，因子的因子也是因子

所以一个数的分解式个数等于因子的分解式个数之和

dp[]初始化0

递推公式：

$$ dp[i] = egin{cases} 1 & i=0 \ sum_{j=0,factor[i] \% factor[j] == 0}^{i-1}dp[j] & i>=1 end{cases} $$

// 动态规划
#include <iostream>
#include <algorithm>

using namespace std;

int solve(int n)
{
	// factor数组存因子, dp数组存分解式个数, cnt记录因子个数
	int factor[2000], dp[2000], cnt = 0, i;
	// 找出n的因子
	for (i = 1; i * i < n; i++)			// 循环次数缩减到sqrt(n)
	{
		if (n % i == 0)
		{
			factor[cnt++] = i;			// i为因子
			factor[cnt++] = n / i;		// n/i也为因子
		}
	}
	if (i * i == n)
		factor[cnt++] = i;				// 如果i*i==n, i也为因子
	
	sort(factor, factor + cnt);			// 把因子从小到大排序
	fill(dp, dp + cnt, 0);				// 把dp数组初始化为0, 初始因子分解式个数都为0

	dp[0] = 1;							// 第一个因子(1)自己的分解式只有一个
	for (i = 1; i < cnt; i++)			// 从第二个因子开始, 循环找第i个因子的因子是否为前i-1个因子
		for (int j = 0; j < i; j++)
			if (factor[i] % factor[j] == 0)	// 如果第i个因子的因子是前i-1个因子中的, 第i个的分解式个数加上满足条件的
				dp[i] += dp[j];
	
	return dp[cnt - 1];					// dp[0]从0开始, cnt要减1
}

int main()
{
	ios::sync_with_stdio(false);		// 防止TLE
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	cout << solve(n);
	return 0;
}