桁和 / Digit Sum [ABC 044, ARC 060 : D]

問題

http://arc060.contest.atcoder.jp/tasks/arc060_b

f(b,n)がある
　n ＜ b のとき f(b,n) = n
　n ≧ b のとき f(b,n) = f(b, floor(n / b)) + (n mod b)
この関数はnをb進数表記したときの各桁の総和を返す関数とも言える
f(B,N)=Sとなる2以上の最小のBを答えよ
無ければ-1

1 <= N <= 10^11
1 <= S <= 10^11

帰納的考察（解説見た）

1. 2分探索っぽい感じがあるので、とりあえずf(b,n)が単調増加・単調減少かを見たい
2. f(b,n)を実装して、bを変化させてみる
3. ・・・
4. ぜんぜん単調じゃないぞ…にぶたん無理じゃん
5. 最小のbを答えよという所が気になる
――壁――
6. 言ってることはわかるけど、どう考えたらこんな解法思いつくのかが分からん
7. O(ルートn)解法なにかなーって所から考えるんかな？

8. まず、N = Sなら答えはN+1
9. 2 <= B <= sqrt(N) で答えを全探索する -> 全探索1
10. sqrt(N) < Bでの答えは、B進数表記で2桁になることを利用して数える
11. 2桁目をpとして計算を色々考えると B = (N - S) / p + 1になる（解説参照）
12. 1 <= p < sqrt(N) で答えを全探索する -> 全探索2
13. 最小のものが答え

14. バグらせてハマった原因

• 関数fを実装するときにb == 1を上手いこと処理しないと計算が終わらない
• 2回の全探索を行うが、答えがわかった瞬間に返すと最小値じゃないかもしれないのでダメ

実装

http://arc060.contest.atcoder.jp/submissions/858657

#define INF 1LL<<60
typedef long long ll;
ll N, S;
ll f(ll b, ll n) {
	if (b < 2) return INF;
	ll ret = 0;
	while (n >= b) ret += n % b, n /= b;
	return ret + n;
}
//-----------------------------------------------------------------
ll solve() {
	if (N == S) return N + 1; 
	ll ans = INF;

	// 全探索1
	rep(B, 2, sqrt(N) + 1) if (f(B, N) == S) ans = min(ans, (ll)B);
	// 全探索2
	rep(p, 1, sqrt(N)) {
		ll B = (N - S) / p + 1;
		if (f(B, N) == S) ans = min(ans, B);
	}

	if (ans == INF)
		return -1;
	else
		return ans;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> S;
	cout << solve() << endl;
}