PKU 3421 X-factor Chains

http://poj.org/problem?id=3421
与えられた条件をみたすような数列の最長の長さとその長さになるような数列の組み合わせの個数を求めろというような問題。

素因数分解して、組み合わせとか順列とかやる。

bool pr[1<<21];
int npr[1<<21];
int pos;

main(){
  for(int i=2;i<(1<<21);++i){
    if(pr[i])continue;
    npr[pos++]=i;
    for(int j=i*2;j<(1<<21);j+=i)pr[j]=true;
  }

  int n;
  while(cin>>n){
    ll len=0,ans=1;
    for(int i=0;npr[i]*npr[i]<=n;++i){
      if(n%npr[i])continue;
      int t=0;
      while(n%npr[i]==0){
        ++len;
        ans*=len;
        ++t;
        n/=npr[i];
      }
      while(t)ans/=t--;
    }
    if(n!=1)++len,ans*=len;
    cout<<len<<' '<<ans<<endl;
  }
}