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