川添さん問題04 エース・ナンバー

■■■問題■■■

整数nに対して、16進数のAをn個並べた数をF(n)と定義します。

例えば、F(5)は16進数でAAAAAです。この数を10進数で表すと699050です。
同様に、F(10)を10進数で表すと733007751850です。この数を100万で割った余りは751850です。

標準入力から、10進数の自然数n (1 <= n <= 100億) が与えられます。
標準出力に、F(n)を10進数で表したものを100万で割った余りを出力してください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            //699050
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            //751850
        }
        else if (InputPattern == "Input3") { //最悪計算量
            WillReturn.Add("10000000000");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] SuuretuArr;
    static long StartInd;

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

        CreateSuuretu();
        Console.WriteLine(Solve(N));

        //for (int I = 1; I <= 9999; I++) {
        //    long wkResult1 = SolveNaive(I);
        //    long wkResult2 = Solve(I);

        //    if (wkResult1 != wkResult2) {
        //        Console.WriteLine("ナイーブだと{0}で非ナイーブだと{1}", wkResult1, wkResult2);
        //    }
        //}
    }

    //1桁目からの数列を求めて、循環開始の項番号も返す
    static void CreateSuuretu()
    {
        var SuuretuList = new List<long>();

        long NewVal = 10;

        while (true) {
            int wkInd = SuuretuList.IndexOf(NewVal);
            if (wkInd >= 0) {
                StartInd = wkInd;
                SuuretuArr = SuuretuList.ToArray();
                break;
            }

            SuuretuList.Add(NewVal);
            NewVal = (NewVal * 16) % 1000000;
        }
    }

    static long Solve(long pN)
    {
        long Mod1 = 0, Mod2 = 0;

        //循環部の前を処理
        for (long I = 0; I <= StartInd - 1; I++) {
            if (I + 1 <= pN)
                Mod1 = (Mod1 + SuuretuArr[I]) % 1000000;
        }

        //循環部を処理
        if (StartInd + 1 <= pN) {
            //循環部の項数
            long CycleCnt = SuuretuArr.Length - StartInd;

            //循環部のMod
            long CycleMod = 0;

            //残りの項数
            long RestCnt = pN - StartInd;

            //循環部のmod
            for (long I = StartInd; I <= SuuretuArr.GetUpperBound(0); I++) {
                CycleMod = (CycleMod + SuuretuArr[I]) % 1000000;
            }
            Mod2 = (CycleMod * (RestCnt / CycleCnt)) % 1000000;

            //残りの循環部のmod
            for (long I = StartInd; I <= StartInd + RestCnt % CycleCnt - 1; I++) {
                Mod2 = (Mod2 + SuuretuArr[I]) % 1000000;
            }
        }
        return (Mod1 + Mod2) % 1000000;
    }

    //ナイーブに解く
    static long SolveNaive(long pN)
    {
        long PrevVal = 10;
        long Answer = 0;
        for (long I = 1; I <= pN; I++) {
            Answer = (Answer + PrevVal) % 1000000;
            PrevVal = (PrevVal * 16) % 1000000;
        }
        return Answer;
    }
}

解説

初項10、公比16の等比数列ですが、
100万を法とした余りで考えれば、循環することをふまえてます。

「エース・ナンバー」問題解説 --- CodeIQ MAGAZINE