ABC044-D 桁和

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("87654");
            WillReturn.Add("30");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("87654");
            WillReturn.Add("138");
            //100
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("87654");
            WillReturn.Add("45678");
            //-1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("31415926535");
            WillReturn.Add("1");
            //31415926535
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("1");
            WillReturn.Add("31415926535");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mS;

    static void Main()
    {
        List<string> InputList = GetInputList();

        mN = long.Parse(InputList[0]);
        mS = long.Parse(InputList[1]);

        // 場合01
        if (mN < mS) {
            Console.WriteLine(-1);
            return;
        }

        // 場合02
        if (mN == mS) {
            Console.WriteLine(mN + 1);
            return;
        }

        // 場合03
        if (mN > mS) {
            var KouhoBSet = new HashSet<long>();

            // B*B <= Nの分は、全探索
            for (long LoopB = 2; LoopB * LoopB <= mN; LoopB++) {
                long CurrKetaSum = DeriveKetaSum(LoopB);
                if (CurrKetaSum == mS) {
                    KouhoBSet.Add(LoopB);
                }
            }

            // B*B > N の分は、連立方程式から必要条件を求める
            long[] YakusuuArr = DeriveYakusuuArr(mN - mS);
            foreach (long EachYakusuu in YakusuuArr) {
                long CurrKetaSum = DeriveKetaSum(EachYakusuu + 1);
                if (CurrKetaSum == mS) {
                    KouhoBSet.Add(EachYakusuu + 1);
                }
            }

            if (KouhoBSet.Count == 0) {
                Console.WriteLine(-1);
            }
            else {
                Console.WriteLine(KouhoBSet.Min());
            }
        }
    }

    // B進数で表現した時の桁和を返す
    static long DeriveKetaSum(long pB)
    {
        long CopiedN = mN;
        long KetaSum = 0;
        while (CopiedN > 0) {
            KetaSum += CopiedN % pB;
            CopiedN /= pB;
        }
        return KetaSum;
    }

    // 約数を列挙する
    static long[] DeriveYakusuuArr(long pTarget)
    {
        var YakusuuSet = new HashSet<long>();
        for (long I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }
        long[] YakusuuArr = YakusuuSet.ToArray();
        Array.Sort(YakusuuArr);
        return YakusuuArr;
    }
}

解説

最初に
NとSの大小関係で、3つの場合に分けます。

場合1 N < S
場合2 N = S
場合3 N > S

N > S の場合は、さらに
B*B <= N かで、場合に分けます。

B*B <= N の場合は、全探索で候補のBを列挙します。
B*B > N の場合は、
B進数での表現において
1桁目の桁の重みは1
2桁目の桁の重みはB
3桁目の桁の重みはB*B
なので、最大でも2桁と分かります。

ここで、NとSから数式を作って、必要条件を探します。
B進数で、2桁目をX、1桁目をYで表現できるとすると
SとNから下記の式が成り立ちます。

S = X+Y
N = X*B + Y
N > S で
引き算して、式を作ると
N - S = X * (B - 1)
となり、
B-1は、N - S の約数であるという必要条件が発見できました。
後は、約数列挙して、約数+1を、Bの候補として、全探索してます。