ABC044-D:桁和 / Digit Sum

問題

https://beta.atcoder.jp/contests/abc044/tasks/arc060_b

整数 n に対して b進数の桁和 f(b, n) が与えられる。f(b, n) = s を満たすような最小の b を求めよ。

制約

  • 1 <= n <= 1011
  • 1 <= s <= 1011

考え方

n が大きいので単純に全探索はできない。そこで  \sqrt{n} で場合分けする。

(i) 2 <= b <=  \sqrt{n} の場合
この場合は b で全探索が可能である。b を 2 から順番に参照し、桁和を求める関数 f の結果が s に等しい場合は、その b を出力すればいい。

(ii)  \sqrt{n} < b の場合
この場合は p, q (1<= p < b, 0 <= q < b) を用いて
n = b * p + q ・・・①
と表すことができる。
また桁和が s になることから
p + q = s ・・・②
とできる。
n = b * p + q >= b * p > p2 より
(1<=) p <  \sqrt{n} となる。
①、②より b = (n-s)/p + 1 となるから p を全探索して、最小の b を求めればよい。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long n = in.nextLong();
            long s = in.nextLong();

            if (s == n) {
                out.println(n+1);
                return;
            }
            if (s > n) {
                out.println(-1);
                return;
            }

            // b <= √n
            for (int b = 2; b <= (int)Math.sqrt(n); b++) {
                if (f(n, b) == s) {
                    out.println(b);
                    return;
                }
            }

            // b > √n
            long ans = LINF;
            for (int p = 1; p < Math.sqrt(n); p++) {
                if ((n-s) % p == 0) {
                    long b = (n-s) / p + 1;
                    if (f(n, b) == s) {
                        ans = Math.min(b, ans);
                    }
                }
            }

            out.println(ans == LINF ? -1 : ans);
        }

        long f(long n, long mod) {
            long ret = 0;
            while (n > 0) {
                ret += n % mod;
                n /= mod;
            }
            return ret;
        }

ポイント

  • ルートで場合分け。
  • b 進数の表現

類題

雑記