Problem39 和が1000未満のピタゴラス数

問題

辺の長さが{a,b,c}と整数の3つ組である直角三角形を考え,
その周囲の長さをpとする. p = 120のときには3つの解が存在する:

{20,48,52}, {24,45,51}, {30,40,50}
p <= 1000 で解の数が最大になるpを求めよ.

ソース

#include <string>
#include <vector>
#include <Windows.h>
#include <stdio.h>
#include <valarray>

struct AnswerStruct
{
    int P;
    std::string Answer;
};

void main()
{
    std::vector<AnswerStruct> AnsVect;
    for (int P = 1; P <= 1000; P++) {
        for (int A = 1; A <= P; A++) {
            for (int B = A; B <= P; B++) {
                if (A + B > P) break;
                int C = P - A - B;
                if (A * A + B * B != C * C) continue;

                AnswerStruct WillAdd;
                WillAdd.P = P;
                char wkCharArr[100];
                wsprintf(wkCharArr,"%3d,%3d,%3d",A, B, C);
                WillAdd.Answer = wkCharArr;
                AnsVect.push_back(WillAdd);
            }
        }
    }

    //Pの、最頻値の件数を求める
    std::valarray<int> CntArr(0,1000+1);
    for(std::vector<AnswerStruct>::iterator it=AnsVect.begin();it!=AnsVect.end();it++){
        CntArr[it->P]++;
    }
    int MaxCnt=0;
    for(int I=0;I<=(int)CntArr.size()-1;I++){
        if(MaxCnt < CntArr[I]) MaxCnt = CntArr[I];
    }
    for(int I=0;I<=(int)CntArr.size()-1;I++){
        if(MaxCnt == CntArr[I]) printf("解の数が最大になるP=%d\n",I);
    }

    for(std::vector<AnswerStruct>::iterator it=AnsVect.begin();it!=AnsVect.end();it++){
        //Pの件数 = 最頻値の件数なら出力
        if(CntArr[it->P] == MaxCnt) printf("P=%d,Answer=%s\n",it->P,it->Answer.c_str());
    }
}

実行結果

解の数が最大になるP=840
P=840,Answer= 40,399,401
P=840,Answer= 56,390,394
P=840,Answer=105,360,375
P=840,Answer=120,350,370
P=840,Answer=140,336,364
P=840,Answer=168,315,357
P=840,Answer=210,280,350
P=840,Answer=240,252,348

解説

ループを多用して最頻値となるPを求めてます。