ABC420-G sqrt(n * n + n + X)

問題へのリンク

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("4");
            //4
            //-4 -1 0 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("-10000");
            //8
            //-10001 -773 -593 -101 100 592 772 10000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20250824");
            //8
            //-20250824 -4050164 -13304 -884 883 13303 4050163 20250823
        }
        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 X = long.Parse(InputList[0]);

        long Uhen = -4 * X + 1;

        // 右辺が0の場合
        if (Uhen == 0) {
            Console.WriteLine(0);
            return;
        }

        long[] YakusuuArr = DeriveYakusuuArr(Math.Abs(Uhen));

        var AnwerSet = new HashSet<long>();
        foreach (long EachYakusuu in YakusuuArr) {
            Action<long, long> CheckAct = (pA, pB) =>
            {
                long pN;
                if (DeriveN(pA, pB, out pN)) {
                    AnwerSet.Add(pN);
                }
            };

            long AbsUhen = Math.Abs(Uhen);

            // 右辺が0未満の場合
            if (Uhen < 0) {
                CheckAct(-EachYakusuu, AbsUhen / EachYakusuu);
                CheckAct(EachYakusuu, -AbsUhen / EachYakusuu);
                CheckAct(-AbsUhen / EachYakusuu, EachYakusuu);
                CheckAct(AbsUhen / EachYakusuu, -EachYakusuu);
            }

            // 右辺が0超えの場合
            if (Uhen > 0) {
                CheckAct(EachYakusuu, AbsUhen / EachYakusuu);
                CheckAct(-EachYakusuu, -AbsUhen / EachYakusuu);
                CheckAct(AbsUhen / EachYakusuu, EachYakusuu);
                CheckAct(-AbsUhen / EachYakusuu, -EachYakusuu);
            }
        }

        Console.WriteLine(AnwerSet.Count);

        if (AnwerSet.Count > 0) {
            var AnswerList = new List<long>(AnwerSet.OrderBy(pX => pX));
            Console.WriteLine(LongEnumJoin(" ", AnswerList));
        }
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

    // 連立方程式
    // 2*n+1-2*m = A
    // 2*n+1+2*m = B
    // をnについて解く
    static bool DeriveN(long pA, long pB, out long pN)
    {
        pN = -1;
        long Uhen = pA + pB - 2;
        if (Uhen % 4 == 0) {
            pN = Uhen / 4;
            return true;
        }
        return false;
    }

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

解説

n*n + n + X = m*m とおいて、式変形をします。
n*n + n - m*m = -X
n*n + n + 0.25 - 0.25 - m*m = -X
4*n*n + 4*n + 1 - 1 - 4*m*m = -4X
(2n + 1 ) ^ 2 - 4*m*m = -4X + 1
(2n + 1 ) ^ 2 - (2m) ^ 2 = -4X + 1
(2n + 1 + 2m) * (2n + 1 - 2m) = -4X + 1

なので,(-4X + 1)が0なら、解なし
(-4X + 1)が0でない場合は、約数列挙して、2つの数の積の形にして、
2n + 1 + 2m = 約数1
2n + 1 - 2m = 約数2
の連立方程式を加減法で解けば、nの値が分かります。