典型90問 058 Original Calculator（★4）

問題へのリンク

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("5 3");
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 100");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("99999 1000000000000000000");
            //84563
        }
        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 K = wkArr[1];
        Console.WriteLine(Solve(N, K));
    }

    static long Solve(long pN, long pK)
    {
        if (pN == 0) {
            return 0;
        }

        var AppearList = new List<long>();
        var AppearSet = new HashSet<long>();

        long[] PreCycleArr;
        long[] CycleArr;

        long CurrVal = pN;
        while (true) {
            if (AppearSet.Contains(CurrVal)) {
                PreCycleArr = AppearList.TakeWhile(pX => pX != CurrVal).ToArray();
                CycleArr = AppearList.SkipWhile(pX => pX != CurrVal).ToArray();
                break;
            }
            AppearList.Add(CurrVal);
            AppearSet.Add(CurrVal);

            CurrVal = DeriveNextVal(CurrVal);
        }

        if (pK <= PreCycleArr.Length) {
            long PrevVal1 = PreCycleArr[pK - 1];
            return DeriveNextVal(PrevVal1);
        }
        long RestK = pK - PreCycleArr.Length;
        long PrevVal2 = CycleArr[(RestK - 1) % CycleArr.Length];
        return DeriveNextVal(PrevVal2);
    }

    // 現在値を引数として、次の値を返す
    static long DeriveNextVal(long pCurrVal)
    {
        long KetaSum = 0;
        long NextVal = pCurrVal;
        while (pCurrVal > 0) {
            KetaSum += pCurrVal % 10;
            pCurrVal /= 10;
        }

        NextVal += KetaSum;
        NextVal %= 100000;
        return NextVal;
    }
}

解説

途中からサイクルのなるので
サイクルを検知するようにしてます。