TopCoder SRM 707 Div1 Medium MultiplyAddPuzzle

コーナーケースが面倒。
https://community.topcoder.com/stat?c=problem_statement&pm=14527

問題

整数S,T,A,Bが与えられる。

Sに対し以下の処理を繰り返しTにしたい。

• Aを加える
• B倍する

処理を最小何度行えばよいか。

解法

Bの値で大まかに場合分けする。

• B=1の場合
  • B倍は意味がないので、(T-S)/Aが整数ならその回数だけA加える。
• B=0の場合
  • 最初に0倍することでS=0にできる点以外はB=1の場合と同じ。両者調べて小さい方を応えればよい。
• B≧2の場合
  • 乗算の回数を総当たりしよう。仮に乗算をm回使えるなら、Sから生成可能な整数は乗算を使う合間に加算を行う回数をp[i]としてとなる。
  • あとはとなるp_iの最小値を求めよう。右辺をB進数とみなし、p[0]から順に決めていけばよい。

途中乗算の過程でオーバーフローを起こして計算ミスしないよう注意。自分も注意してたつもりが1WAやらかした。

class MultiplyAddPuzzle {
	public:
	long long minimalSteps(long long s, long long t, long long a, long long b) {
		
		if(s==t) return 0;
		
		if(b<=1) {
			if(b==0 && t==0) return 1;
			if(a) {
				if(s<=t && (t-s)%a==0) return (t-s)/a;
				if(b==0 && t%a==0) return 1+t/a;
			}
			return -1;
		}
		// a>=1, b>=2
		ll mi=1LL<<60;
		ll cur=1,num=0;
		while(1) {
			if(s*cur/cur!=s) break;
			if(s*cur>t) break;
			
			if(t==s*cur) {
				mi=min(mi,num);
			}
			if(a && (t-s*cur)%a==0) {
				ll left=(t-s*cur)/a;
				ll step=num,r=1;
				int i;
				while(r<cur) {
					step += left%b;
					r*=b;
					left/=b;
				}
				step+=left;
				mi=min(mi,step);
			}
			
			if(cur*b>t || cur*b/b!=cur) break;
			cur*=b;
			num++;
		}
		if(mi==1LL<<60) mi=-1;
		return mi;
	}
}

まとめ

難しくはないが。