euler-0075.cpp

// ////////////////////////////////////////////////////////
// # Title
// Singular integer right triangles
//
// # URL
// https://projecteuler.net/problem=75
// http://euler.stephan-brumme.com/75/
//
// # Problem
// It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
//
// 12 cm: (3,4,5)
// 24 cm: (6,8,10)
// 30 cm: (5,12,13)
// 36 cm: (9,12,15)
// 40 cm: (8,15,17)
// 48 cm: (12,16,20)
//
// In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found;
// for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
//
// 120 cm: (30,40,50), (20,48,52), (24,45,51)
//
// Given that `L` is the length of the wire, for how many values of `L <= 1,500,000` can exactly one integer sided right angle triangle be formed?
//
// # Solved by
// Stephan Brumme
// March 2017
//
// # Algorithm
// Euclid's formula produces all triplets `a`, `b`, `c` such that `a^2 + b^2 = c^2` (see https://en.wikipedia.org/wiki/Pythagorean_triple)
// All basic triplets can be generated by:
// `a = m^2 - n^2`
// `b = 2mn`
// `c = m^2 + n^2`
// where `m > n` and `(m+n) mod 2 == 1` and `m`, `n` are coprime (i.e. `gcd(m,n) = 1`)
//
// To find all "non-basic" triplets: multiply `a`, `b`, `c` by any integer `k > 1`.
//
// My pre-computation step 1 counts how many ''combinations'' exists for every perimeter `a+b+c` below 1500000.
// The function ''gcd'' is known from previous problems.
//
// In step 2, only those perimeters which are unique are copied to a container named ''once''.
//
// The final step is running the tests: find the smallest perimeter exceeding the user input (=1500000 for the original problem).
// Its index is the desired result.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

// find greatest common divisor
template <typename T>
T gcd(T a, T b)
{
  while (a != 0)
  {
    T c = a;
    a = b % a;
    b = c;
  }
  return b;
}

int main()
{
  // pre-computation step 1: find all triangle combinations up to 1500000
  const unsigned int MaxLength = 5 * 1000 * 1000;
  // [length] => [number of valid combinations]
  std::vector<unsigned int> combinations(MaxLength, 0);

  for (unsigned int m = 2; m < sqrt(MaxLength); m++)
    for (unsigned int n = 1; n < m; n++)
    {
      // only valid m and n
      if ((m + n) % 2 != 1)
        continue;
      if (gcd(m, n) != 1)
        continue;

      // compute basic triplet
      auto a = m*m - n*n;
      auto b = 2*m*n;
      auto c = m*m + n*n;
      auto sum = a + b + c;

      // and all of its multiples
      unsigned int k = 1;
      while (k*sum <= MaxLength)
      {
        combinations[k*sum]++;
        k++;
      }
    }

  // pre-computation step 2: extract those with exactly one combination
  std::vector<unsigned int> once;
  for (size_t i = 0; i < combinations.size(); i++)
    if (combinations[i] == 1)
      once.push_back(i);

  // running the test-cases is a simple look-up
  unsigned int tests = 1;
  std::cin >> tests;
  while (tests--)
  {
    unsigned int limit = 1500000;
    std::cin >> limit;

    // find first triangle perimeter exceeding 1500000 with exactly one combination
    auto pos = std::upper_bound(once.begin(), once.end(), limit);
    // count how many one-combo-triangles are smaller
    auto result = std::distance(once.begin(), pos);
    // and print that number
    std::cout << result << std::endl;
  }
}