ABC179-E Sequence Sum

問題へのリンク

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("6 2 1001");
            //1369
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000 2 16");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10000000000 10 99959");
            //492443256176507
        }
        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 X = wkArr[1];
        long M = wkArr[2];

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

        long[] PreCycleArr;
        long[] CycleArr;

        long CurrVal = X;
        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 = (CurrVal * CurrVal) % M;
        }

        // 周期に入る前の分を加算
        long RestN = N;
        long TakeCnt = Math.Min(RestN, PreCycleArr.Length);
        long Answer = PreCycleArr.Take((int)TakeCnt).Sum();
        RestN -= PreCycleArr.Length;
        if (RestN == 0) {
            Console.WriteLine(Answer);
            return;
        }

        // 周期の分を加算
        if (CycleArr.Length <= RestN) {
            long OneCycleSum = CycleArr.Sum();
            Answer += OneCycleSum * (RestN / CycleArr.Length);
            RestN %= CycleArr.Length;
        }

        // 残りの分を加算
        Answer += CycleArr.Take((int)RestN).Sum();

        Console.WriteLine(Answer);
    }
}

解説

modの数列が、途中からサイクルになることに着目してます。

類題

ABC241-E Putting Candies