ABC428-D 183184

問題へのリンク

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("4");
            WillReturn.Add("4 80");
            WillReturn.Add("183 5000");
            WillReturn.Add("18 10");
            WillReturn.Add("824 5000000000");
            //3
            //2
            //0
            //1421
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static Dictionary<long, long> mBeki10Dict = new Dictionary<long, long>();

    static void Main()
    {
        mBeki10Dict = GetBekiDict(10);

        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long C = wkArr[0];
            long D = wkArr[1];
            long Result = Solve(C, D);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long pC, long pD)
    {
        long Answer = 0;

        long Default_Sahen = 1;
        long Default_Uhen = 9;

        // (C+X)の桁数で場合分け
        for (long LoopKeta = 1; LoopKeta <= 11; LoopKeta++) {
            // 不等式の両辺からCを引く
            long Curr_Sahen = Default_Sahen - pC;
            long Curr_Uhen = Default_Uhen - pC;

            // 下限調整
            long XMin = Math.Max(1, Curr_Sahen);

            // 上限調整
            long XMax = Math.Min(pD, Curr_Uhen);

            //Console.WriteLine("{0}桁の場合、XMin={1}、XMax={2}", LoopKeta, XMin, XMax);

            // 有効な定義域かを判定
            if (XMin <= XMax) {
                // 値は1刻みで連続で取れるので、最小値と最大値を求める
                long MinVal = CalcFunc(pC, pC + XMin);
                long MaxVal = CalcFunc(pC, pC + XMax);

                long SquareVal, SquareRootVal;
                SquarRootClass.Sqrt_LowerBound(MinVal, out SquareVal, out SquareRootVal);
                long Jyoukai = SquareRootVal;

                SquarRootClass.Sqrt_LowerMax(MaxVal, out SquareVal, out SquareRootVal);
                long Kakai = SquareRootVal;

                if (Jyoukai <= Kakai) {
                    Answer += Kakai - Jyoukai + 1;
                }
            }

            Default_Sahen *= 10;
            Default_Uhen = Default_Uhen * 10 + 9;
        }
        return Answer;
    }

    // f(A,B)の結果を返す
    static long CalcFunc(long pA, long pB)
    {
        long pKeta = GetLongKeta(pB);
        long Result = pA * mBeki10Dict[pKeta] + pB;
        return Result;
    }

    ////////////////////////////////////////////////////////////////
    // long型の桁数を返す
    ////////////////////////////////////////////////////////////////
    static long GetLongKeta(long pVal)
    {
        long Limit = 9;
        long KetaSuu = 1;
        while (true) {
            if (Math.Abs(pVal) <= Limit) return KetaSuu;
            KetaSuu++;
            Limit = Limit * 10 + 9;
        }
    }

    ////////////////////////////////////////////////////////////////
    // べき数のDictを返す
    // ex 2を引数にして呼ぶと
    // BekiDict[0]= 1
    // BekiDict[1]= 2
    // BekiDict[2]= 4
    // BekiDict[3]= 8
    // BekiDict[4]=16
    // というdictを返す
    ////////////////////////////////////////////////////////////////
    static Dictionary<long, long> GetBekiDict(long pVal)
    {
        // long型の2正数の掛け算が、Limitを超えるかを返す
        Func<long, long, long, bool> WillOverProdFunc = (pA, pB, pLimit) =>
        {
            return pA > pLimit / pB;
        };

        var BekiDict = new Dictionary<long, long>();
        long CurrBeki = 1;
        long CurrShisuu = 0;
        while (true) {
            BekiDict[CurrShisuu] = CurrBeki;

            if (WillOverProdFunc(CurrBeki, pVal, long.MaxValue)) break;
            CurrBeki *= pVal;
            CurrShisuu++;
        }
        return BekiDict;
    }
}

#region SquarRootClass
// 平方数クラス
internal class SquarRootClass
{
    // long型を引数とし、
    // 引数以上で最小の平方数と、正の平方根を設定
    // 内部では二分探索を使用。
    internal static void Sqrt_LowerBound(long pVal, out long pSquareVal, out long pSquareRootVal)
    {
        if (pVal == 0) {
            pSquareVal = 0;
            pSquareRootVal = 0;
            return;
        }

        long L = 0;
        long R = pVal;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (WillOverProd(Mid, Mid, pVal)) {
                R = Mid;
            }
            else if (Mid * Mid >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        pSquareVal = R * R;
        pSquareRootVal = R;
    }

    // long型を引数とし、
    // 引数以下で最大の平方数と、正の平方根を設定
    // 内部では二分探索を使用。
    internal static void Sqrt_LowerMax(long pVal, out long pSquareVal, out long pSquareRootVal)
    {
        if (pVal == 0) {
            pSquareVal = 0;
            pSquareRootVal = 0;
            return;
        }
        if (pVal == 1) {
            pSquareVal = 1;
            pSquareRootVal = 1;
            return;
        }

        long L = 0;
        long R = pVal;

        while (L + 1 < R) {
            long Mid = (L + R) / 2;

            if (WillOverProd(Mid, Mid, pVal)) {
                R = Mid;
            }
            else if (Mid * Mid > pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        pSquareVal = L * L;
        pSquareRootVal = L;
    }

    // long型の2正数の掛け算が、Limitを超えるかを返す
    private static bool WillOverProd(long pA, long pB, long pLimit)
    {
        return pA > pLimit / pB;
    }
}
#endregion

解説

f(C,C+X)なので、
(C+X)の桁数で場合分けしてます。

桁数で場合分けすれば、
桁数ごとにf(C,C+X)の値は、1刻みで連続するため、
最小値の上界の、平方数の平方根と
最大値の下界の、平方数の平方根を求めれば、
平方数の個数も求めることができます。