质因数分解

x可以被分解质因数为p1^c1 * p2^c2 * … * pk^ck的形式,要使序列最长,我们需要每次都除上一个质因子,因此最大长度为(c1 + c2 + … + ck),而最长序列的方案取决于我们除质因子的顺序,属于排列组合问题,类似选座位问题,座位的总数为maxlen,我们首先考虑质因子p1, 那么它的选法就有$C_{maxlen}^{c1}$种, 然后再看p2, 由于p1已经选好了c1个座位,此时p2的方案数为$C_{maxlen - c1}^{c2}$,以此类推，总的方案数为阶段方案数的乘积.

时间复杂度

由于本题x最大为2^20,因此可以用一个二维数组来预处理1~20的组合数，用线性筛来分解x的质因数,在预处理之后,可以快速的求出每种情况的组合数.

C++ 代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int N = (1 << 20) + 1;

int primes[N], c[25][25], h[25], cnt;
bool st[N];
int x, k;

void init(){
    for(int i = 2; i < N; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; j < cnt && i * primes[j] < N; j++){
            st[i * primes[j]] = true;
            if(i % primes[j] == 0) break;
            }
        }

    c[0][0] = 1;
    for(int i = 1; i <= 20; i++){
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j <= i; j++){
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
            }
        }
}

int main(){
    init();
    while(scanf("%d", &x) != EOF){
        int maxlen = 0, maxcnt = 1;
        int n = x;
        memset(h, 0, sizeof(h));
        k = 0;
        for(int i = 0; i < cnt && primes[i] <= n; i++){
            int p = primes[i];
            int t = 0;
            if(n % p == 0){
                while(n % p == 0){ 
                    n /= p;
                    t++;
                    maxlen++;
                    }
                h[k++] = t;
                }
            }
        n = maxlen;
        for(int i = 0; i < k; i++){
            maxcnt *= c[n][h[i]];
            n -= h[i];
            }
        printf("%d %d\n", maxlen, maxcnt);
        }
    return 0;
}