首页 > 代码库 > 9718 整数因子分解（必做） 分治法
9718 整数因子分解（必做） 分治法
9718 整数因子分解（必做）
时间限制:1000MS 内存限制:1000K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC;JAVA
Description
大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm， 每个xi为大于1的因子，即1<xi<=n 。 例如：当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共有多少种不同的分解式。
输入格式
第一行一个正整数n （1<=n<=1000000）
输出格式
不同的分解式数目
输入样例
12
输出样例
8
考虑先暴力写出前几项。
数字：1、2、3、4、5、6、7、8、9、10、11、12
ans：1、1、1、2、1、3、1、4、2、3 、 1、 8
所以递推式就是fun(val) = val的所有因子的答案加起来（不包括自己， 然后 + 1，就是加上自己）。递归求解即可。
为什么这样是答案呢？
因为其是考虑顺序的，那么ans就是第一个数字是2的分拆数总和 + 第一个数字是3的分拆数总和。
第一个数字是2的分拆数总和是多少？就是2 * （6的分拆数）递归求解。
提示
此题因子讲顺序的.第一个因子可能是2~n之间的数.
比如对12而言,第一个因子可能是2,3,4,6,12.
将第一个因子为2的分解个数,加上第一个因子为3的分解个数,...,直至加到第一个因子为12的分解个数.
而第一个因子为2的分解个数又是多少呢?是6(因为12/2=6)的分解个数,递归求解!
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1000000 + 20; LL dp[maxn]; LL find(int val) { if (dp[val]) return dp[val]; LL ans = 1; for (int i = 2; i <= val / 2; ++i) { if (val % i != 0) continue; dp[i] = find(i); ans += dp[i]; } return ans; } void work() { int n; cin >> n; dp[1] = 1; LL ans = 1; for (int i = 2; i <= n / 2; ++i) { if (n % i != 0) continue; dp[i] = find(i); ans += dp[i]; } cout << ans << endl; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }
9718 整数因子分解（必做） 分治法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。