ARC149-A Repdigit Number

問題へのリンク

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("7 12");
            //888888
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9 12");
            //888888888
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 3");
            //9
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("1000 25");
            //-1
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("30 1");
            //999999999999999999999999999999
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long M = wkArr[1];

        // 長さ[繰り返す数字]なDict
        var AnswerDict = new Dictionary<long, long>();
        for (long I = 1; I <= 9; I++) {
            long Beki10 = 1;
            long ModVal = 0;
            for (long J = 1; J <= N; J++) {
                ModVal += Beki10 * I;
                ModVal %= M;
                if (ModVal == 0) {
                    AnswerDict[I] = J;
                }
                Beki10 *= 10;
                Beki10 %= M;
            }
        }

        if (AnswerDict.Count == 0) {
            Console.WriteLine(-1);
            return;
        }

        var Query1 = AnswerDict.OrderByDescending(pX => pX.Value);
        var Query2 = Query1.ThenByDescending(pX => pX.Key);
        foreach (var EachPair in Query2) {
            var sb = new System.Text.StringBuilder();
            for (long I = 1; I <= EachPair.Value; I++) {
                sb.Append(EachPair.Key);
            }
            Console.WriteLine(sb.ToString());
            return;
        }
    }
}

解説

長さ[繰り返す数字]なDictで解候補を管理しつつ。
mod M で考えて、ナイーブに解候補を全部調べてます。