ARC148-A mod M

問題へのリンク

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("3");
            WillReturn.Add("1 4 8");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("5 10 15 20");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("3785 5176 10740 7744 3999 3143 9028 2822 4748 6888");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        Array.Sort(AArr);

        long Diff = AArr[AArr.GetUpperBound(0)] - AArr[0];

        long[] YakusuuArr = DeriveYakusuuArr(Diff);

        foreach (long EachYakusuu in YakusuuArr) {
            if (EachYakusuu == 1) continue;
            var AnswerSet = new HashSet<long>();
            foreach (long EachA in AArr) {
                AnswerSet.Add(EachA % EachYakusuu);
            }
            if (AnswerSet.Count == 1) {
                Console.WriteLine(1);
                return;
            }
        }

        if (AArr.Distinct().Count() == 1) {
            Console.WriteLine(1);
        }
        else {
            Console.WriteLine(2);
        }
    }

    // 約数を列挙する
    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;
    }
}

解説

法を2にすれば、modは0か1の2通りなので
解は1か2のどっちかだと分かります。

合同方程式
3785 ≡ 5176 (mod 法)
が成立するのは、
法が、(5176と3785の差の)約数の場合なので

数列のminとmaxの差の、約数を全て試して、
modがユニークかをチェックしてます。