POJ 3421 X-factor Chains

問題

整数Xに対してX-factor chainとは次を満たす列のことを言う。
1 = X0 < X1 < …… < Xm = X;
かつXi+1はXiで割りきれる。

正の整数Xが与えられたとき、このような列のうち最大の長さをもつものおよび、
そのような長さを持つ列の数を出力せよ。

制約条件

X≦2^20

方針

長さ最長のX-factor chainは、
Xの素因数をp,q,r,sなどとおけば
1→(p倍する)→(q倍する）→(r倍する）→(s倍する）
というふうに、素因数をかけていくことで作れる。

したがって長さは素因数の数で、列の数は素因数を並べ替える順列の数である。

ソースコード

ll fact(int n){
  ll ret=1;
  rep(i,n)ret*=i+1;
  return ret;
}
int main(){
  int n;
  while(~scanf("%d",&n)){
    vector<int> f;
    for(int i=2;i*i<=n;i++)if(n%i==0){
      int cnt=0;
      while(n%i==0)cnt++, n/=i;
      f.pb(cnt);
    }
    if(n>1)f.pb(1);
    
    int len=0; ll ans=1;
    rep(i,f.size())len+=f[i];
    ans*=fact(len);
    rep(i,f.size())ans/=fact(f[i]);
    printf("%d %lld\n",len,ans);
  }
  return 0;
}