PKU : 3421 - X-factor Chains

問題概要

http://poj.org/problem?id=3421

Xが入力として与えられ, 次のようなm+1個の数を含む数列を考えます.

• 1 = X0, X1, X2, …, Xm = X

Xi番目の項は, X_(i-1)番目の項で割り切ることができ, Xi > X_(i-1)が成り立っています.

このとき, この数列の最大長と, 最大長となる数列が何種類存在するかを答えてください.

アルゴリズム

結論だけいうと

• 数列の最大長は「Xの素因数の数」
• 種類数は「素因数の順列の数」

最後の項は, Xにしなければいけないから, X0〜X_(m-1)の項は, 必ずXの素因数を掛け合わせた数になります. そのため, どうがんばっても, 最大長はXの素因数の数にしかならないです.
初項から, 順番に数列を求めていくとき, 素因数のかける順番を変えれば, 違う数列となるので, 種類数は素因数の順列の数となります.

プログラム

頭悪い方法でやってるかもです.

//階乗計算
ll fact(int x){
  ll res = 1;
  REP(i,2,x+1){
    res *= i;
  }
  return res;
}

int main(){
  int n;

  while(cin>>n){
    vector<int> f; //Nを割り切る素数が, それぞれ何回出現したか
    int sum = 0; //Nの素因数の数

    //素因数計算
    for(int now = 2; now*now <= n; now++){
      if(n % now != 0) continue;

      int c = 0;

      while(n % now == 0){
        n /= now;
        c++;
      }

      f.push_back(c);
      sum += c;
    }

    if(n != 1){
      f.push_back(1);
      sum++;
    }

    //順列数計算と, 重複をはぶく計算
    ll cal = fact(sum);
    rep(i,f.size()){
      cal /= fact(f[i]);
    }
    cout<<sum<<" "<<cal<<endl;
  }
}