3421:X-factor Chains

keyword

整数　素因数分解　C++

概要

正整数Xに対してX-factor chainを1=x_0 < x_1 < ... < x_m = Xかつ、x_i | x_{i+1}で定める。X(<2^20)が与えられたとき、X-factor chainの最大の長さと、それを達成するものはいくつあるか求める問題。
素因数分解したときの指数だけが問題になる。指数の部分を1ずつ増やしていけば良いので最大値は指数の和。組み合わせの数は多項定理のアレ。計算量は素因数分解のO(√X)。

int comb[30][30];

int combination(int n, int k){
    if(comb[n][k]) return comb[n][k];
    if(n==0 || k==0 || k>=n)
        return comb[n][k] = 1;
    return comb[n][k] = (combination(n-1,k) + combination(n-1,k-1));
}

void solve(int x){
    if(x==1){
        puts("0 1");
        return ;
    }
    vector<int> fs;
    for(int i=2;i*i<=x;i++){
        if(x%i == 0){
            fs.push_back(0);
            while(x%i==0){
                fs.back()++;
                x /= i;
            }
        }
    }
    if(x!=1) fs.push_back(1);
    int total = accumulate(fs.begin(), fs.end(), 0);
    printf("%d ",total);
    int num = 1;
    for(int i=0; i<fs.size(); i++){
        num *= combination(total, fs[i]);
        total -= fs[i];
    }
    printf("%d\n",num);
    return ;
}