POJ 3421: X-factor Chains

概要

2^20より小さい正整数Xが与えられる．長さnのX-factor ChainはX_1 < X_2 < ... < X_n = Xで，かつ
X_i | X_{i+1} であるものをいう．
Xの最長のX-factor Chainの長さはいくつか．また，最長のX-factor Chainの個数はいくつあるか．

解法

Xを素因数分解．素因数の冪の合計が長さに，各素因数の重複順列が個数に対応する．

vector<int> sieve_of_eratosthenes(ll n, vector<ll> &prime){
    vector<int> isPrime(n);
    for(ll i = 2; i < n; ++i)
        isPrime[i] = i;
    for(ll i = 2; i < n; ++i)
        if(isPrime[i]){
            prime.push_back(i);
            for(ll j = i * i; j < n; j += i)
                isPrime[j] = 0; 
        }
    return isPrime;
}
ll factorial(ll n){
    ll res = 1;
    while(n > 0) res *= n--;
    return res;
}

vector<ll> prime;
ll X;
int main(){
    sieve_of_eratosthenes(1LL << 20, prime);
    while(~scanf("%lld", &X)){
        ll sum = 0, res;
        vector<ll> v;
        EACH(i, prime){
            if(X <= (*i) * (*i)){
                if(X == *i * *i){
                    v.push_back(2);
                    sum += 2;
                    X = 1;
                }
                if(X != 1){
                    sum ++;
                }
                break;
            }
            if(X % *i == 0){
                ll s = 0;
                while(X % *i == 0){
                    ++s;
                    X /= *i;
                }
                sum += s;
                v.push_back(s);
            }
        }
        res = factorial(sum);
        EACH(i, v)
            res /= factorial(*i);
        printf("%lld %lld\n", sum, res);
    }
    return 0;
}