ABC397-D Cubes

問題へのリンク

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("397");
            //12 11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //-1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("39977273855577088");
            //342756 66212
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        decimal N = decimal.Parse(InputList[0]);

        for (decimal Div1 = 1; Div1 * Div1 * Div1 <= N; Div1++) {
            if (N % Div1 == 0) {
                decimal X, Y;
                bool Result = Solve(Div1, N / Div1, out X, out Y);
                if (Result) {
                    Console.WriteLine("{0} {1}", X, Y);
                    return;
                }
            }
        }
        Console.WriteLine(-1);
    }

    static bool Solve(decimal pDiv1, decimal pDiv2, out decimal pX, out decimal pY)
    {
        pX = pY = -1;
        decimal A = 3;
        decimal B = -3 * pDiv1;
        decimal C = pDiv1 * pDiv1 - pDiv2;

        decimal Heihoukon;
        if (IsHeihousuu(B * B - 4 * A * C, out Heihoukon) == false) {
            return false;
        }

        decimal Bunbo = 2 * A;
        decimal Bunshi = -B + Heihoukon;

        if (Bunshi % Bunbo > 0) {
            return false;
        }
        pX = Bunshi / Bunbo;
        if (pX <= 0) return false;

        pY = pX - pDiv1;
        if (pY <= 0) return false;

        return true;
    }

    // 平方数かを判定して返す
    static bool IsHeihousuu(decimal pTarget, out decimal pHeihoukon)
    {
        pHeihoukon = -1;
        if (pTarget == 1) {
            pHeihoukon = 1;
            return true;
        }

        decimal L = 1;
        decimal R = pTarget;

        while (L + 1 < R) {
            decimal Mid = (L + R) / 2;
            Mid = Math.Truncate(Mid);

            decimal Prod = Mid;
            if (WillOverProd(Prod, Mid, pTarget)) {
                R = Mid;
                continue;
            }
            Prod *= Mid;

            if (Prod >= pTarget) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }

        if (R * R == pTarget) {
            pHeihoukon = R;
            return true;
        }
        return false;
    }

    // 2正数の掛け算が、Limitを超えるかを返す
    static bool WillOverProd(decimal pA, decimal pB, decimal pLimit)
    {
        return pA > Math.Truncate(pLimit / pB);
    }
}

解説

X*X*X - Y*Y*Y = N
を因数分解すると
(X-Y) * (X*X + X*Y + Y*Y) = N

(X-Y) = Dとおくと
X>0 , Y> 0 より
D < X , X*Y > 0 Y*Y > 0

(X-Y) * (X*X)
を考えると
D は Nの3乗根以下と分かる。
なのでDを、1からNの3乗根まで全探索します。

2数の積 = Nなので
DがNの約数であることは必要条件

必要条件を満たすDを使って、
下記の連立方程式を解きます。
X-Y = D
X*X + X*Y + Y*Y = N/D

X-Y = D ⇔ X-D = Y
なので、代入法を使えば
X*X + X*Y + Y*Y = N/D
を2次方程式にできます。

あとは、XとYを求め、
最後に十分性を確認すれば良いです。