AOJ 0211 みんなでジョギング

問題へのリンク

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("2");
            WillReturn.Add("4 3");
            WillReturn.Add("5 4");
            WillReturn.Add("5");
            WillReturn.Add("789 289");
            WillReturn.Add("166 46");
            WillReturn.Add("9 4");
            WillReturn.Add("617 252");
            WillReturn.Add("972 303");
            WillReturn.Add("2");
            WillReturn.Add("8 5");
            WillReturn.Add("32 20");
            WillReturn.Add("0");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int CurrInd = 0;
        while (true) {
            int N = int.Parse(InputList[CurrInd]);
            if (N == 0) break;

            string[] InputArr = InputList.Skip(CurrInd + 1).Take(N).ToArray();
            Solve(InputArr);

            CurrInd += N + 1;
        }
    }


    struct DataInfoDef
    {
        internal long Distance;
        internal long Speed;
    }
    static List<DataInfoDef> mDataInfoList = new List<DataInfoDef>();

    static void Solve(string[] pInputArr)
    {
        mDataInfoList.Clear();

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

        for (long I = 0; I <= pInputArr.GetUpperBound(0); I++) {
            SplitAct(pInputArr[I]);

            DataInfoDef WillAdd;
            WillAdd.Distance = wkArr[0];
            WillAdd.Speed = wkArr[1];
            mDataInfoList.Add(WillAdd);
        }

        long ACycle = 1; // LCMの単位元は1

        long FirstDistance = mDataInfoList[0].Distance;
        long FirstSpeed = mDataInfoList[0].Speed;

        foreach (DataInfoDef EachDataInfo in mDataInfoList.Skip(1)) {
            long Sahen = FirstDistance * EachDataInfo.Speed;
            long Uhen = FirstSpeed * EachDataInfo.Distance;

            long CurrLCM = DeriveLCM2(Sahen, Uhen);
            long CurrACycle = CurrLCM / Sahen;

            ACycle = DeriveLCM2(ACycle, CurrACycle);
        }
        //Console.WriteLine("ACycle={0}", ACycle);

        long TotalTime = ACycle * FirstDistance / FirstSpeed;
        //Console.WriteLine("TotalTime={0}", TotalTime);

        foreach (DataInfoDef EachDataInfo in mDataInfoList) {
            Console.WriteLine(ACycle * FirstDistance * EachDataInfo.Speed
                / FirstSpeed / EachDataInfo.Distance);
        }
    }

    // 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;
        }
    }
}

解説

まずは、2人だけで考えます。
2人が一致することは必要条件であります。

距離をD1 , 速度をS1
距離をD2 , 速度をS2
とします。

1人目の周回数をA,2人目の周回数をBとします。

すると
D1 / S1 * A = D2 / S2 * B
変形して
D1 * S2 * A = D2 * S1 * B

左辺と右辺 は、LCM(D1 * S2 ,D2 * S1) の倍数ですが
なるべく小さいほうが良いので
A = LCM / D1 / S2
になります。

同様に1人目と3人目で一致することを考えた時の
Aの周回数を考えると

LCM(1人目と2人目でのAの最小周回数 ,
    1人目と3人目でのAの最小周回数 ,
    1人目と4人目でのAの最小周回数 ,
    1人目と5人目でのAの最小周回数)
となるので、
これから全員の周回数を求めることができます。

実装で
除算での切り捨てが発生しないように注意する必要があります。