X的因子链

要想求出严格递增且任意前面数可以整除后面数的因子序列，就要用到算术基本定理，先随便找一个质因子，然后序列的第二个数一定是前面的质因子再乘上另一个质因子，以此类推，序列最后一个数一定是所有质因子的乘积。所以，序列的长度是质因子的个数。排列的方式不一定是质因子个数的阶乘，因为在选择过程中，会有重复，比如先选2，再选3和先选3，再选2，第二个数都是6。重复的个数可以根据一个样例来看，比如 2，4，4，12，24，48。（注意，这个序列是质因子乘完的序列） 由于两个4可以互换位置，假设其他数不动，那么重复的个数就是2的阶乘个，所以只要将质因子个数的阶乘除以每个质因子个数的阶乘的乘积就得出了答案。

#include<cstdio>
using namespace std;
typedef long long LL;
const int N = (1 << 20) + 10;
int p[N], cnt, minp[N];
bool t[N];
void prime(int n) {
	for (int i = 2; i <= n ; i ++) {
		if (!t[i]) {
			p[cnt ++] = i;
			minp[i] = i;
		}
		for (int j = 0; p[j] *i <= n; j ++) {
			t[p[j] * i] = true;
			minp[i * p[j]] = p[j];
			if (i % p[j] == 0) {
				break;//保证筛掉的是合数，并且是用最小质因子筛的
			}
		}
	}
}
int main() {
	int n;
	prime(N);
	while (scanf("%d", &n)!= -1) {
        int  k = 0;
        int num[30], sum = 0;
        while(n > 1)
        {
            int p = minp[n];
            num[k] = 0;
            while(n % p == 0)
            {
                n /= p;
                num[k] ++;
                sum ++ ;
            }
            k ++;
        }
        LL res = 1;
        for(int i = sum; i > 0; i --)res *= i;
        for(int i = 0; i < k; i++)
        {
            for(int j = 1; j <= num[i]; j ++)res /= j;
        }
        cout <<sum <<" "<<res<<endl;
	}
	return 0;
}