PKU3092 Non-divisible 2-3 Power Sums
数N(<=2^32-1)を
2^a*3^bの和で表せ。ただし2^a*3^bのどれかがどれかで割りきれてはいけない
探索します。メモ化しなくてもOKです
まず、nが2で割りきれるとき、すべての2^a*3^bのaはa>=1なので、
n/2の場合に帰結できます。
nが2で割りきれないとき、2^a*3^bのうち一つだけaが0のものがあるはずなので、
一つサイズを小さくできます
そんな感じ
vector<pair<int,int> > res; int dfs(int n,int thr){ if(n==0) return 1; if(n==1){ if(thr<0) return 0; res.pb(mp(0,0)); return 1; } int cnt=res.size(); if(n%2==0){ if(dfs(n/2,thr)){ REPN(i,res.size(),cnt) ++res[i].fr; return 1; } }else{ lint mul=1; REP(i,thr) mul*=3; for(int i=thr;i>=0;--i,mul/=3){ if(mul>n) continue; if(dfs(n-mul,i-1)){ res.pb(mp(0,i)); return 1; } } } return 0; } int main(){ int t;scanf("%d",&t); REP(setn,t){ res.clear(); int n;scanf("%d",&n); dfs(n,30); printf("%d %d",setn+1,(int)res.size()); REP(i,res.size()) printf(" [%d,%d]",res[i].fr,res[i].sc); putchar('\n'); } return 0; }