結果

問題 No.1233 割り切れない気持ち
コンテスト
ユーザー aketijyuuzou
提出日時 2026-04-09 19:58:14
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 199 ms / 3,153 ms
コード長 2,889 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,535 ms
コンパイル使用メモリ 173,024 KB
実行使用メモリ 232,456 KB
最終ジャッジ日時 2026-04-09 19:58:34
合計ジャッジ時間 19,591 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (89 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

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

// https://yukicoder.me/problems/no/1233
// yukicoder 1233 割り切れない気持ち
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);
            //Console.WriteLine("{0}の場合のSum={1}", EachA, Result);
            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;
    }
}
0