ABC230-E Fraction Floor Sum

問題へのリンク

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("3");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10000000000");
            //231802823220
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = long.Parse(InputList[0]);

        long CurrI = 1;

        long Answer = 0;
        while (true) {
            long DivVal = mN / CurrI;
            long EndI = ExecNibunhou(DivVal - 1) - 1;
            // Console.WriteLine("{0}の区間は、{1}から{2}", DivVal, CurrI, EndI);
            Answer += DivVal * (EndI - CurrI + 1);
            CurrI = EndI + 1;
            if (CurrI > mN) break;
        }
        Console.WriteLine(Answer);
    }

    // 二分法で、N/Iが引数以下になる最小のIを返す
    static long ExecNibunhou(long pVal)
    {
        // 特殊ケースの対応
        if (mN / 1 <= pVal) return 1;
        if (pVal == 0) return mN + 1;

        long L = 1;
        long R = mN;

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

            long CurrVal = mN / Mid;
            if (CurrVal <= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}

解説

Iの増加に対して、広義単調減少であることに着目して、
二分探索で、値ごとの区間を求めることを繰り返してます。