ABC290-D Marking

問題へのリンク

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("9");
            WillReturn.Add("4 2 1");
            WillReturn.Add("4 2 2");
            WillReturn.Add("4 2 3");
            WillReturn.Add("4 2 4");
            WillReturn.Add("5 8 1");
            WillReturn.Add("5 8 2");
            WillReturn.Add("5 8 3");
            WillReturn.Add("5 8 4");
            WillReturn.Add("5 8 5");
            //0
            //2
            //1
            //3
            //0
            //3
            //1
            //4
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long N = wkArr[0];
            long D = wkArr[1];
            long K = wkArr[2];

            if (D > N) {
                D %= N;
            }

            long Result = Solve(N, D, K);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long pN, long pD, long pK)
    {
        // 互いに素の場合
        long GCD = DeriveGCD(pN, pD);
        if (GCD == 1) {
            return (pD * (pK - 1)) % pN;
        }

        long Kousuu = pN / GCD;

        // コリジョンの発生回数
        long CollisionCnt = pK / (Kousuu);
        if (pK % Kousuu == 0) CollisionCnt--;

        long RestK = pK - Kousuu * CollisionCnt;

        long Result = (CollisionCnt + pD * (RestK - 1)) % pN;

        return Result;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

解説

Dが、N以上の場合
D%=N を実行しても良いです。

考察すると
NとDが互いに素ならコリジョンは発生しない。
NとDが互いに素でない場合、コリジョンが発生する。
と分かります。

コリジョン回数は、周期とKの値から求めることができます。

コリジョン回数ごとに、分けて考えることができるので、
後は、配列が無限にあると考えて、
添字の値を、等差数列の一般項のように計算し、mod N を取れば解が分かります。