Problem 75

e75.cpp

#include <iostream>
#include <vector>
#include <map>
#include <thread>
#include <mutex>
#include <algorithm>
#include <iomanip>
using namespace std;

const long limit = 1500000;
mutex mtx;
vector<long> squares;
map<long, long> used_perimeters;

void InitializeSquares(){
    for (long i = 0; i <= limit; ++i) {
        squares.push_back(i*i);
    }
}

void FindTriangles(long start_position, long stop_position){
    /*Seeks right triangles whose sides are integers and add their perimeters to the map. Perimeter must be less or equal to 'limit'.
     Searches hypotenuse and longer catet in the vector of squares and checks if the second catet is there too.
    */
    
    auto start = begin(squares) + start_position;
    auto stop = begin(squares) + stop_position;
    
    //c (hypotenuse) can't be longer than half of perimeter, so we have to search only up to squares[limit/2]
    for (auto c = start; c < stop; ++c) {
        
        //Print every thousandth index to estimate running time.
        if ((c - begin(squares))%1000==0){
            mtx.lock();
            cout << "Debug: " << c - begin(squares) << endl;
            mtx.unlock();
        }
        
        //b must be less than c.
        for (auto b = begin(squares) + 1; b < c; ++b) {
            //And a less than b.
            if (binary_search(begin(squares)+1, b, *c - *b)) {
                auto a = find(begin(squares)+1, b, *c - *b);                
                //Sum indexes 
                if ((a-begin(squares)) + (b - begin(squares)) + (c - begin(squares)) <= limit) {
                    mtx.lock();
                    ++used_perimeters[(a-begin(squares)) + (b - begin(squares)) + (c - begin(squares))];
                    mtx.unlock();
                }
            }
        }
    }
    
}



int main(){
    InitializeSquares();
    
    thread t1(FindTriangles,1,340000);
    thread t2(FindTriangles,340000,530000);
    thread t3(FindTriangles,530000,690000);
    thread t4(FindTriangles,690000,750000);
    
    t1.join();
    t2.join();
    t3.join();
    t4.join();
    
    long answer = 0;
    for (auto i = begin(used_perimeters); i != end(used_perimeters); ++i) {
        if (i->second==1) {
            ++answer;
        }        
        //Print perimeters along with quantity of possible triangles for debugging purposes.
        cout << i->first << ": " << i->second << endl;
    }
    cout << answer << endl;
    return 0;
    
}