MultiplyAddPuzzle [SRM 707 : Div1 Med] - はまやんはまやんはまやん

問題

ある数sについて以下の手順をしてある数tにしたい。

1. +aする
2. *bする

最小のステップ数は？

0 <= s,t,a,b <= 10^18

考察

1. コーナーケースがやばいので、s > t, b = 0, b = 1, a = 0らへんはうまいことやる

2. 気づくべき点が「書ける回数はあまり多くないのでは？」という所
3. 10^18が最大数なので2 <= bであれば、64回より多くは掛けないはず
4. 手順2の回数を固定して考える

5. n回*bをするとすると、以下のように問題を読み替えることができる
$t=sb^n + a(bの多項式)$
6. 後はbの多項式部分が項数最小となり、かつ、以上の等式を満たすパターンを考えればいい
7. つまり、以下の問題に最終的に帰着する
$定数x = \sum^{n}_{k = 0}a_kb^k 上での \sum^{n}_{k=0}a_k の最小値$
8. これは以下のようにして求まる

ll cal(ll x, ll b, int n) {
	ll res = 0;
	rep(i, 0, k) {
		res += (x % b);
		x /= b;
	}
	return res + x;
}

9. 手順2の回数を全パターン試して最小が答え
10. long longのオーバーフローに注意

参考

https://togetter.com/li/1076293
Um_nikさんのコード（最強に分かりやすい）