yukicoder 1233 割り切れない気持ち

問題へのリンク

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");
            WillReturn.Add("1 5 3");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9");
            WillReturn.Add("9 9 9 9 9 9 9 9 9");
            //0
        }
        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 long mMaxA;
    static long mSumA;
    static long UB;

    // 度数分布表
    static long[] mRunSumArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = GetSplitArr(InputList[1]);

        mMaxA = AArr.Max();
        mSumA = AArr.Sum();
        UB = mMaxA;

        // 度数分布表
        long[] CntArr = new long[UB + 1];
        Array.ForEach(AArr, pX => CntArr[pX]++);

        // 度数の累積和
        mRunSumArr = (long[])CntArr.Clone();
        for (long I = 1; I <= UB; I++) {
            mRunSumArr[I] += mRunSumArr[I - 1];
        }

        long Answer = 0;

        // 法ごとに全探索
        foreach (long EachA in AArr) {
            long Result = DeriveAnswer(EachA);
            Answer += Result;
        }
        Console.WriteLine(Answer);
    }

    // 法を引数として解を返す
    static Dictionary<long, long> mMemo = new Dictionary<long, long>();
    static long DeriveAnswer(long pHou)
    {
        if (pHou == 1) return 0;

        if (mMemo.ContainsKey(pHou)) {
            return mMemo[pHou];
        }

        long Answer = mSumA;

        long RangeSta = 0;
        long RangeEnd = pHou - 1;
        long Omomi = 0;
        while (true) {
            long CurrAnswer = GetRangeSum(RangeSta, RangeEnd);
            Answer -= pHou * Omomi * CurrAnswer;

            RangeSta += pHou;
            RangeEnd += pHou;
            Omomi++;

            if (RangeSta > mMaxA) break;
        }
        return mMemo[pHou] = Answer;
    }

    // 区間和を返す
    static long GetRangeSum(long pRangeSta, long pRangeEnd)
    {
        if (pRangeSta > UB) return 0;

        pRangeEnd = Math.Min(pRangeEnd, UB);

        long RangeSum = mRunSumArr[pRangeEnd];
        if (pRangeSta > 0) {
            RangeSum -= mRunSumArr[pRangeSta - 1];
        }
        return RangeSum;
    }
}

解説

法ごとに、割り算の商が1の個数、2の個数、3の個数を
順に求めるのは、調和級数なのでO(N logN)なので、
最初に度数分表の累積和を求めておいて、
解くことができます。