PKU 1604 Just the Facts

http://poj.org/problem?id=1604
N!の最も小さい0じゃない位の桁の数字を答える問題。

何だかあまりをとりながら計算してもうまくいかないで、多倍長を引っ張ってきて、高速化して結構ギリギリでAccepted
要正攻法調査。

const int size=8;
string ret;
string add(const string&a,const string&b){
  ret.clear();
  int as=a.size(),bs=b.size();
  int c=0;
  rep(i,max(as,bs)){
    int t=c;
    if(i<as)t+=a[i]-'0';
    if(i<bs)t+=b[i]-'0';
    c=t/10;
    t%=10;
    ret+=t+'0';
    if(ret.size()>size)return ret;
  }
  if(c)ret+=c+'0';
  return ret;
}

string mulcret;
string multc(char m,const string&a,int l0){
  m-='0';
  mulcret.clear();
  while(l0--)mulcret+='0';

  int c=0;
  int as=a.size();
  rep(i,as){
    int t=c+m*(a[i]-'0');
    c=t/10;
    t%=10;
    mulcret+=t+'0';
    if(mulcret.size()>size)return mulcret;
  }
  if(c)mulcret+=c+'0';
  return mulcret;
}

string mulret;
string mult(const string&a,string b){
  mulret.clear();
  int as=a.size();
  
  rep(i,as){
    mulret=add(mulret,multc(a[i],b,i));
    if(mulret.size()>size)return mulret;
  }
  return mulret;
}

string ans[10000];

string toret;
string to_str(int n){
  toret="";
  while(n){
    toret+=n%10+'0';
    n/=10;
  }
  return toret;
}

main(){
  ans[0]=ans[1]="1";
  string str;
  for(int i=2;i<10000;i++){
    int tt=i;
    while(tt%10==0)tt/=10;
    str=to_str(tt);
    ans[i]=mult(ans[i-1],str);
    int pos=0;
    while(ans[i][pos]=='0')pos++;
    if(pos)ans[i]=ans[i].substr(pos);
  }

  int n;
  while(cin>>n)printf("%5d -> %c\n",n,ans[n][0]);
}