第12回PAST I 毎日のリンゴ

問題へのリンク

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("10");
            WillReturn.Add("4 5 8");
            WillReturn.Add("8 9 10");
            WillReturn.Add("4 10 7");
            WillReturn.Add("10 1 5");
            WillReturn.Add("6 4 9");
            WillReturn.Add("304607 77 89");
            WillReturn.Add("291969 231 9");
            WillReturn.Add("424790 216 294");
            WillReturn.Add("76881 213 111");
            WillReturn.Add("312895 58 1");
            //14
            //36
            //12
            //20
            //24
            //13402703
            //875907
            //61169622
            //4151490
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mA;
    static long mM;
    static long mLCM;

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

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1)) {
            long[] wkArr = EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
            mN = wkArr[0];
            mA = wkArr[1];
            mM = wkArr[2];
            mLCM = DeriveLCM2(mA, mM);
            long Result = Solve();
            sb.Append(Result);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

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

        long[] PreCycleArr;
        long[] CycleArr;

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

            CurrDay++;
            CurrHash = GetHash(CurrDay);
        }

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

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

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

        return Answer;
    }

    // ハッシュ値の列挙を引数として、「悲しさ」の総和を返す
    static long GetSum(IEnumerable<long> pEnum)
    {
        long WillReturn = 0;
        foreach (long EachHash in pEnum) {
            long Val1 = EachHash / Geta;
            long Val2 = EachHash % Geta;

            if (Val1 == 0) Val1 = mLCM;
            if (Val2 == 0) Val2 = mLCM;

            WillReturn += Math.Abs(Val2 - Val1);
        }
        return WillReturn;
    }

    const long Geta = 1000000000;

    // 日を引数として、リンゴ価格と、クーポン総額のハッシュ値を返す
    static long GetHash(long pDay)
    {
        // リンゴ価格
        long ApplePrice = mA * pDay;

        long Syou = ApplePrice / mM;
        if (ApplePrice % mM > 0) Syou++;

        long CouponPrice = Syou * mM;

        // ハッシュ値はmod LCMで考える
        long Val1 = ApplePrice % mLCM;
        long Val2 = CouponPrice % mLCM;

        return Val1 * Geta + Val2;
    }

    // 2つの数のLCMを求める
    static long DeriveLCM2(long p1, long p2)
    {
        long GCD = DeriveGCD(p1, p2);
        return (p1 / GCD) * p2;
    }

    // ユークリッドの互除法で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;
        }
    }
}

解説

リンゴが5円ずつで、クーポンが8円ずつで考察します。

 5  8
10 16
15 16
20 24
25 32
30 32
35 40
40 40
45 48
50 56

5と8のLCMでmodを取れば周期性があると分かるので、
周期性を使って解いてます。