ARC159-B GCD Subtraction

問題へのリンク

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("15 9");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1 1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("12345678910 10987654321");
            //36135
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long A = wkArr[0];
        long B = wkArr[1];
        long Result = Solve(A, B);
        Console.WriteLine(Result);
    }

    static long Solve(long pA, long pB)
    {
        long A = Math.Max(pA, pB);
        long B = Math.Min(pA, pB);

        if (A == B) {
            return 1;
        }

        long[] YakusuuArr = DeriveYakusuuArr(A - B);
        long Answer = 0;

        while (true) {
            if (B == 0) {
                break;
            }
            if (A == B) {
                Answer++;
                break;
            }

            long CurrGCD = DeriveGCD2(A, B);

            // 残り操作回数[GCD]なDict
            var RestCntDict = new SortedDictionary<long, long>();
            RestCntDict[CurrGCD] = B / CurrGCD;

            foreach (long EachYakusuu in YakusuuArr) {
                if (EachYakusuu <= CurrGCD) continue;

                if (CurrGCD > 1) {
                    if (EachYakusuu % CurrGCD > 0) continue;
                }

                RestCntDict[EachYakusuu] = (A % EachYakusuu) / CurrGCD;
            }

            var TargetItem = RestCntDict.OrderBy(pX => pX.Value).First();

            A -= CurrGCD * TargetItem.Value;
            B -= CurrGCD * TargetItem.Value;
            Answer += TargetItem.Value;
        }
        return Answer;
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD2(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;
        }
    }

    // 約数を列挙
    static long[] DeriveYakusuuArr(long pTarget)
    {
        var YakusuuSet = new HashSet<long>();
        for (long I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                YakusuuSet.Add(I);
                YakusuuSet.Add(pTarget / I);
            }
        }
        long[] YakusuuArr = YakusuuSet.ToArray();
        Array.Sort(YakusuuArr);
        return YakusuuArr;
    }
}

解説

A >= B
としても解は変わらないので、
AとBの大小関係を固定して考えます。

具体例として、
118と78で考えます

  A   B  GCD
118  78    2
116  76    4
112  72    8
104  64    8
 96  56    8
 88  48    8
 80  40   40
 40   0

まず、A-Bは不変量だと分かります。
AとBは減算により減りますが、
A-Bは不変であり、GCDは、下記のように図形で考えると
敷き詰め可能な最大の正方形の1辺ですので、

---------------
|         |   |
|         |   |
|         |   |
|         |   |
---------------

A-B の 約数のみが、
この問題の操作でのGCDになりうると分かります。

また、2の倍数から、2を引いても、2の倍数ですので、
この問題の操作での、次のGCDは、前のGCDの倍数という関係になります。

以上により、
●倍数関係の次のGCDにならずに操作が終了する場合の、Bが0になるまでの操作回数
●倍数関係の次のGCDになる場合の、操作回数
を求めて、最小の操作回数まで操作をスキップし、
TLEにならずに解を求めることができます。