039.cpp

#include <iostream>
#include <set>
using namespace std;

const unsigned MAX = 1000;

unsigned gcd(unsigned m,unsigned n)
{
        //assume m>n
        unsigned r=m%n;
        while (r>0) {
                m=n;
                n=r;
                r = m%n;
        }
        return n;
}

int main()
{
        multiset<unsigned> set_p;
        set<set<unsigned> > lookup_table;

        for (unsigned m=1;m<=21;m++)
                for (unsigned n=m-1;n>0;n--) {
                        //the triples are primitive if m,n are coprime and exactly one of them is even
                        if ((m&1) == (n&1))continue;
                        if (gcd(m,n)!=1) continue;

                        //pythagorean triples by euler's formula
                        unsigned a=m*m-n*n;
                        unsigned b=2*m*n;
                        unsigned c=m*m+n*n;
                        unsigned p = a+b+c;

                        for (unsigned pk=p;pk<=MAX;pk+=p) {
                                if (pk==120)cout << a << ' '<<b <<' '<< c<<endl;
                                set_p.insert(pk);
                        }

                }
        //now count and find p with max no of triples
        unsigned MAX_p=0;
        unsigned best_p=1;
        for (unsigned p=1;p<=MAX;p++) {
                unsigned cnt=set_p.count(p);

                if (cnt>MAX_p) {
                        MAX_p = cnt;
                        best_p = p;
                        //cout << p << '\t' << cnt << endl;
                }
        }
        cout << best_p << endl;
        return 0;
}