D - 桁和 / Digit Sum AtCoder Regular Contest 060

D - 桁和 / Digit Sum

概略

2以上のbと1以上の整数nで、nをb進数で表した時の各桁の和がsとなる最小のbをもとめよ

制約

• $1\le n\le {10}^{11}$
• $1\le s\le {10}^{11}$
• $n,s$ はいずれも整数である

解法

制約が10^11なので全探索は間に合わない。とりあえずルートを取って場合分けする

b <= ルートn

ルートn < b

上は全探索できる。

下はよく見るとbがルートnより大きいため2桁になる。

よって

pb + q = n

p   + q = s　　が成り立ち

n - s = (b - 1)p となり、b-1がn-sの約数になることが分かる。それらを全て調べればよい。

問題の芯

ルートなら間に合うなと思ったらとりあえず試してみる。

探索する範囲が大きい時、場合分けすると簡潔に出来ることがある。

public class Main
{
    static StringBuilder sb = new StringBuilder();
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 12345678;
    static long LINF = 123456789123456789L;
    static long MINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y4 = {0, 1, 0, -1};
    static int[] x4 = {1, 0, -1, 0};
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] F;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;
 
    static long n, s;
    static int[] A;
 
 
    public static void main(String[] args)
    {
        n = sc.nextLong();
        s = sc.nextLong();
        //ルートnまで n = 2 s = 1　のときなどに困るので範囲は大きく取る
        for (int b = 2; b <= Math.sqrt(n+1000000); b++)
        {
            if (check(b))
            {
                System.out.println(b);
                return;
            }
        }
        if (n == s)
        {
            System.out.println(n + 1);
            return;
        }
        TreeSet<Long> que = new TreeSet<>();
 
        //ルートnより大きい
        //b-1 が n-sの約数になる
        for (int b = 2; b <= Math.sqrt(n - s)+1000000; b++)
        {
            if ((n - s) % (b - 1) != 0) continue;
            if (check(b))
            {
                System.out.println(b);
                return;
            }
//約数のもう片側も追加する
            que.add((n - s) / (b - 1) + 1);
        }
        for (Long b : que)
        {
            if (check(b))
            {
                System.out.println(b);
                return;
            }
        }
 
        System.out.println("-1");
 
    }
 
    public static boolean check(long b)
    {
        long res = 0;
        long tn = n;
        while (tn > 0)
        {
            res += tn % b;
            tn /= b;
        }
        return res == s;
    }