Problem211 約数の2乗の和

問題

正の整数 n に対して, ★2(n)を約数の2乗の和とする. 例えば,

★2(10) = 1 + 4 + 25 + 100 = 130

である.
0 < n < 64000000 で, ★2(n) が平方数である全ての n の和を求めよ.

ソース

using System;

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        long AnswerVal = 0;
        for (int I = 1; I < 64000000; I++) {
            if (I % 100000 == 1)
                Console.WriteLine("{0}。残りは{1}。現在の合計={2}", sw.Elapsed, 64000000 - I, AnswerVal);

            long YakusuuSum = DeriveYakusuuSum(I);
            if (IsHeihouSuu(YakusuuSum)) AnswerVal += I;
        }
        Console.WriteLine(AnswerVal);
    }

    static long DeriveYakusuuSum(int pVal)
    {
        int WillReturn = 0;
        for (int I = 1; I * I <= pVal; I++) {
            if (pVal % I == 0) {
                WillReturn += I * I;
                int PairVal = pVal / I;
                if (PairVal != I) WillReturn += PairVal * PairVal;
            }
        }
        return WillReturn;
    }

    //2分法で平方数かの判定
    static bool IsHeihouSuu(long pVal)
    {
        long LeftP=0;
        long RightP = pVal;
        long 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;
    }
}

実行結果

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

解説

答え 1922364685