PKU 2325 Persistent Numbers
http://poj.org/problem?id=2325
ある数字から、数字の各桁をかけていってその積を計算する。
この時、ある数字Nが与えられたとき、各桁の積を計算してNになるような最小の整数を求めろというような問題。
まず、Nが一桁の数字の積で表されるためには因数に2,3,5,7しか持たない必要がある。
ここで2,3,5,7からもとの数字を構築するときに、出来るだけ大きい桁を後に置いていけば良い。
あとは1000桁くらい入力があるというので、多桁/一桁を実装して因数の数を数えれば良い。
string型からの脱却をはかろうとしてみました。
char in[2000]; int di[]={2,3,5,7}; bool bigdiv(char in[],int p){ char ans[2000]; int sz=strlen(in); int mo=0; int ps=0; rep(i,sz){ mo=mo*10+(in[i]&15); ans[ps++]=mo/p+'0'; mo%=p; } if(mo!=0)return false; ans[ps++]=0; if(ans[0]=='0')memcpy(in,ans+1,ps); else memcpy(in,ans,ps); return true; } main(){ while(scanf("%s",in)){ if(strcmp(in,"-1")==0)break; if(strlen(in)<2){ printf("1%s\n",in); continue; } int sm[4]={0}; rep(i,4){ while(bigdiv(in,di[i])){ //cout<<in<<' '<<di[i]<<endl; sm[i]++; } } if(strcmp(in,"1")!=0){ printf("There is no such number.\n"); continue; } char ans[1000]; int ps=0; while(sm[1]>1){ sm[1]-=2; ans[ps++]='9'; } while(sm[0]>2){ sm[0]-=3; ans[ps++]='8'; } while(sm[3]){ --sm[3]; ans[ps++]='7'; } while(sm[0] && sm[1]){ --sm[0]; --sm[1]; ans[ps++]='6'; } while(sm[2]){ --sm[2]; ans[ps++]='5'; } while(sm[0]>1){ sm[0]-=2; ans[ps++]='4'; } while(sm[1]){ --sm[1]; ans[ps++]='3'; } while(sm[0]){ --sm[0]; ans[ps++]='2'; } sort(ans,ans+ps); ans[ps]=0; puts(ans); } }