9718 整数因子分解（必做）

时间限制:1000MS 内存限制:1000K

提交次数:0 通过次数:0

题型: 编程题语言: G++;GCC;VC;JAVA

Description

大于1的正整数 n 都可以分解为 n = x1 * x2 * ... * xm， 每个xi为大于1的因子，即1
    
     <=n 。例如：当n=12时，共有8种不同的分解式：12 = 1212 = 6*212 = 4*312 = 3*412 = 3*2*212 = 2*612 = 2*3*212 = 2*2*3对于给定正整数n，计算n共有多少种不同的分解式。

输入格式

第一行一个正整数n （1<=n<=1000000）

输出格式

不同的分解式数目

输入样例

输出样例

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 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  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;}