トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Problem142 完全平方数コレクション

問題

x + y, x - y, x + z, x - z, y + z, y - z
が全て平方数となる整数の組 x > y > z > 0で, 最小の x + y + z を求めよ.


ソース

using System;

class Program
{
    static void Main()
    {
        for (int SumVal = 6; SumVal < int.MaxValue; SumVal++) {
            Console.WriteLine("SumVal={0}を検証中", SumVal);
            for (int X = 3; X < SumVal; X++) {
                for (int Y = 2; Y < X; Y++) {
                    if (IsHeihouSuu(X + Y) == false) continue;
                    if (IsHeihouSuu(X - Y) == false) continue;

                    for (int Z = 1; Z < Y; Z++) {
                        if (IsHeihouSuu(X + Z) == false) continue;
                        if (IsHeihouSuu(X - Z) == false) continue;
                        if (IsHeihouSuu(Y + Z) == false) continue;
                        if (IsHeihouSuu(Y - Z) == false) continue;

                        Console.WriteLine("Answer={0} (X={1},Y={2},Z={3})", X + Y + Z, X, Y, Z);
                        return;
                    }
                }
            }
        }
    }

    //2分法で平方数かの判定
    static bool IsHeihouSuu(int pVal)
    {
        int LeftP = 0;
        int RightP = pVal;
        int MidP;

        while (LeftP <= RightP) {
            MidP = (LeftP + RightP) / 2;
            //Console.WriteLine("探索対象={0},LeftP={1},MidP={2},RightP={3}", pVal, LeftP, MidP, RightP);
            long NijyouVal = MidP * MidP;
            if (NijyouVal == pVal) return true;
            if (NijyouVal > pVal) {
                RightP = MidP - 1;
            }
            else {
                LeftP = MidP + 1;
            }
        }
        return false;
    }
}


実行結果

計算量が多すぎるので、作り直しが必要です。


解説

答え 1006193