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