第15回PAST I 最大公約数の最大値

問題へのリンク

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 2");
            WillReturn.Add("2 3 4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 3");
            WillReturn.Add("5 5 5");
            //5
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 4");
            WillReturn.Add("225707 265514 765350 617700 837712 187034 799142 35549 784661 961512");
            //2
        }
        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 void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long K = wkArr[1];

        long[] AArr = GetSplitArr(InputList[1]);
        long MaxA = AArr.Max();

        // 配列Aの度数分布表
        long[] ACntArr = new long[MaxA + 1];
        foreach (long EachA in AArr) {
            ACntArr[EachA]++;
        }

        // 約数の度数分布表
        var YakusuuCntArr = new long[MaxA + 1];
        for (long I = 2; I <= MaxA; I++) {
            YakusuuCntArr[I] = 0;
            for (long J = I; J <= MaxA; J += I) {
                YakusuuCntArr[I] += ACntArr[J];
            }
        }

        for (long I = YakusuuCntArr.GetUpperBound(0); 2 <= I; I--) {
            if (YakusuuCntArr[I] >= K) {
                Console.WriteLine(I);
                return;
            }
        }
        Console.WriteLine(1);
    }
}

解説

まず、配列Aの最大値を求めます。
次に、配列Aの各値の度数分布表を作ります。

それから、2から配列Aの最大値までの数で
エラトステネスの篩の要領で倍数を列挙しつつ、
この倍数が配列Aに存在したら、約数の度数分布表の件数に計上してます。

最後に、約数の度数分布表で件数がK以上な、最大の約数を解としてます。