Project Euler Problem 9

 Loop qua tất cả các cặp a<b và tính c bằng sqrt(a^2+b^2)

Nếu c là số nguyên và a+b+c<=3000 thì lưu lại largest product abc

Câu hỏi tại sao lại là nhỏ hơn 3000

a+b+c multiple solution có thể tồn tại và tích lớn nhất abc sẽ trả lại

Cần thiết có bước tính toán trước tất cả các đáp án vòng ngoài để xử lý lượng lớn test case

Dùng vector là mảng động tự cấp phát để lưu giá trị

Giả sử max a =1000 hoặc maxb =1000 hoặc max c=1000 thì có thể max a+b+c = 3000

#include <iostream>

#include <vector>

#include <cmath>

int main()

{

  // precompute all pairs a<b<c where a+b+c <= 3000

  const int MaxPerimeter = 3000;

  // -1 means "no triplets" for that perimeter

  const int NoSolution   =   -1;

  // cache[0] remains unused

  std::vector<int> cache(MaxPerimeter + 1, NoSolution);

  // scan all pairs a<b

  for (int a = 1; a < MaxPerimeter; a++)

    for (int b = a + 1; b < MaxPerimeter - a; b++)

    {

      // find c

      int c2 = a*a + b*b;

      // approximate square root as integer

      int c = sqrt(c2);

      // was it the correct square root ? (kiểm tra lại c có khai căn )

      if (c*c != c2)

        continue;

      // check summing condition

      int sum = a + b + c;

      if (sum > MaxPerimeter)

        break;

      // better solution than before ?

      if (cache[sum] < a*b*c)

        cache[sum] = a*b*c;

    }

  unsigned int tests;

  std::cin >> tests;

  while (tests--)

  {

    unsigned int n;

    std::cin >> n;

    // just lookup results (-1 if no solution)

    std::cout << cache[n] << std::endl;

  }

  return 0;

}