PKU 3092 Non-divisible 2-3 Power Sums

http://poj.org/problem?id=3092
1以上の整数nが与えられるので、互いに素な2と3の冪乗の和で表される形に分解しろというような問題。

あまり原理がわかっていないのですが、以下のような貪欲で一応通りました。
2で割り切れる間はnを2で割って、aを増やす。
3で割り切れる間はnを3で割って、bを増やす。
どちらでも割り切れなくなったら、nより小さい最大の3の累乗を引いて再帰的にこの操作を繰り返す。
あとは指数を復元して出力。

vector<PI> getans(ll n){
  vector<PI> ret;
  if(n==1){
    ret.pb(mp(0,0));
    return ret;
  }

  int a=0,b=0;
  while(n%2==0){
    n/=2;
    ++a;
  }
  while(n%3==0){
    n/=3;
    ++b;
  }
  if(n==1){
    ret.pb(mp(a,b));
    return ret;
  }
  ll t=1;
  int tb=0;
  while(t*3<=n){
    ++tb;
    t*=3;
  }
  ret.pb(mp(a,b+tb));

  vector<PI> di=getans(n-t);
  FOR(it,di)ret.pb(mp(it->F+a,it->S+b));
  return ret;
}

void solve(int Case){
  ll n;
  cin>>n;
  vector<PI> ans=getans(n);
  cout<<Case<<' ';
  cout<<SZ(ans);
  FOR(it,ans)printf(" [%d,%d]",it->F,it->S);
  puts("");
}

main(){
  int T;
  cin>>T;
  rep(ca,T)
    solve(ca+1);
}