1. 问题描述

一个大于1的正整数 $n$ 可以分解为 $n=x_1 \cdot x_2 \cdots x_m$ 。例如，当 $n=12$ 时，共有8种不同的分解式：

$12 = 12 \qquad \qquad 12 = 3 \times 2 \times 2 \\ 12 = 6 \times 2 \qquad \qquad 12 = 2 \times 6 \\ 12 = 4 \times 3 \qquad \qquad 12 = 2 \times 3 \times 2 \\ 12 = 3 \times 4 \qquad \qquad 12 = 2 \times 2 \times 3$

算法设计：对于给定的正整数n，算出共有多少种不同的分解式。
数据输入：由文件input.txt给出输入数据。第一行有个正整数 $n(1 \le n \le 2000000000$ )。
结果输入：将计算的不同的分解式的数目输出到文件output.txt中。

1.1. 问题分析

上面描述的分解式不考虑乘法的交换律，所以可以把第一个分解因子看作一个可以被12整除数字的遍历，剩下的因子就是一个递归问题，求解剩下因子的分解式即可，然后把每种因子的分解结果数相加，递归的返回条件是，因子等于1。

int solveInterger(int input){
    if(input <= 0){
        std::cout<<"input is illegal"<<std::endl;
        return -1;
    }
    int result = 0;
    if(input == 1)
        return 1;
    else
        for(int i = input; i > 1 && input % i == 0 ; i--){
                result = result + solveInterger(input/i);  //每种可整除因子递归结果求和
        }
    return result;
}

1.2. 算法分析

算法中的循环边界是 $(1,n]$ ，其中 $n$ 是输入的数字，但是能够进入到循环中的次数 $T$ 肯定小于 $n$ 。进入循环之后通过递归调用一个更少规模的子问题，输入变成了 $\frac{n}{i}$ 。但是这其中必然存在重复多算的过程，即递归的是不独立的子问题，如下面的情形取 $n =24$ ：
$24 = 2 \times 2 \times 6 \qquad 24 = 4 \times 6$