PKU 2992 Divisors

http://poj.org/problem?id=2992
nCkの約数の個数を求める。(0<=k<=n<=431)

cinの遅さを改めて実感しました。
あと、高速化するのが大変でした。

素因数分解して事前計算して、頑張りました。

map<int,int> fac[432];
ll ans[432][432];

map<int,int> ret;
map<int,int> fact(int in){
  ret.clear();
  for(int i=2;i*i<=in;i++){
    if(in%i)continue;
    do{
      ret[i]++;
      in/=i;
    }while(in%i==0);
  }
  if(in>1)ret[in]++;
  return ret;
}

map<int,int> tt;
main(){
  rep(i,432){
    fac[i]=fact(i);
  }

  rep(n,432){
    tt.clear();
    rep(k,n+1){
      if(ans[n][min(k,n-k)])break;
      if(0<k)FOR(miter,fac[n-k+1])tt[miter->F]+=miter->S;
      FOR(miter,fac[k])tt[miter->F]-=miter->S;
      ll tans=1;
      FOR(miter,tt){
        tans*=miter->S+1;
      }
      ans[n][k]=tans;
    }
  }

  int n,k;
  while(~scanf("%d%d",&n,&k))cout<<ans[n][min(k,n-k)]<<endl;
}