ARC060 D. 桁和
問題
2以上の整数bと、1以上の整数nに対し、関数f(b,n)を以下のように定める。
- n < bのとき、f(b, n) = n
- n >= bのとき、f(b, n) = f(b, floor(n/b)) + (n mod b)
これは、直感的には、nをb進表記したときの各桁の和を表す。
整数nとsが与えられる。f(b, n)=sとなる2以上の整数bの最小値を求めよ。
存在しない場合は-1を出力せよ。
制約
- 1 <= n <= 10^11
- 1 <= s <= 10^11
解法
どこから攻めればよくわからないので、実験として、サンプル(n=87654)でbを2～1000ぐらい表示してみると、早い段階でほぼ2桁になっていることがわかる。
2桁になるのは、b>=sqrt(N)付近で、そこまでは全探索しても問題ないので、2<=b<=sqrt(N)あたりまでは全探索する。
ここで見つからなければ、b>=sqrt(N)を探索する。
b=N+1のときは1桁になって、それ以降のbではsもNより大きくならないので、2桁の部分を考えればよい。
2桁であるので、n=p*b+qとp+q=sであることがわかる。
pとqがあるが、2式あるので削除でき、n=p*b+(s-p)と書ける。
pをループで回すと考えると、b=(n-(s-p))/pとなって、pが決まればbも一意に決まる。(bが1以下の場合は無視)
pはどこまで探索する必要があるかを考えると、n=p*b+qで、b>=sqrt(N)であるので、実はpもsqrt(N)程度までで十分であることがわかる。
