川添さん問題05 セカンド・イクエイション

■■■問題■■■

3つの自然数a,b,cに対し、これらを係数に持つ次の二次方程式を考えます。

a*x*x + b x + c ＝ 0 ・・・ (※)

例えば、(a,b,c) = (1,6,4) のとき、方程式(※)は、x*x + 6x + 4 = 0 となります。
この方程式は実数解を持ちます。x = -3+ルート(5) と x = -3-ルート(5) の2つです。
一方で、(a,b,c) = (1,6,10) のとき、方程式(※)は実数解を持ちません。

b <= 3 の範囲で、
方程式(※)が少なくとも1つの実数解を持つような自然数の組 (a,b,c)は、全部で4組あります。
(a,b,c) = (1,2,1), (1,3,1), (1,3,2), (2,3,1) です。

自然数 m に対し、
b <= m の範囲で方程式(※)が少なくとも1つの実数解を持つような
自然数の組(a,b,c)の個数をF(m)と定義します。

例えばF(3)=4、F(4)=12、F(10)=287、F(100)=620174 です。

標準入力から、自然数m (1 <= m <= 3000) が与えられます。
標準出力に F(m) の値を出力するプログラムを書いてください。

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            //12
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            //287
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("100");
            //620174
        }
        else if (InputPattern == "Input5") { //最悪計算量
            WillReturn.Add("3000");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //b*b - 4*a-c >=0
        //b*b >= 4*a*c
        //bとaを固定して、cの解の数を求める

        long AnswerCnt = 0;
        for (int b = 1; b <= m; b++) {
            int Sahen = b * b / 4; //小数部を切り捨て可能な不等式

            //計算量を減らすため、a<=cとする
            for (int a = 1; Sahen >= a * a; a++) {
                int MaxC = Sahen / a; //小数部を切り捨て可能な不等式

                int wkCnt = MaxC - a + 1; //a<=cを満たすcのみカウント

                wkCnt *= 2; //a<=cを解除して場合の数を調整
                wkCnt--; //a==cの分を引く

                AnswerCnt += wkCnt;
            }
        }
        Console.WriteLine(AnswerCnt);
    }
}

解説

計算量を減らすため、a<=cとして、
後で場合の数を調整してます。

「セカンド・イクエイション」問題解説 --- CodeIQ MAGAZINE