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]); }