#75 단일길이 정수 직각 삼각형

이번 문제는 피타고라스 삼각형을 만들고, 그것을 에라스토테네스의 체처럼 사용하는 문제입니다.  난이도 25% 문제입니다.  하지만, 피타고라스 삼각형을 만드는 공식만 알면 크게 어려움 없이 풀 수 있는 문제입니다.  이 프로그램을 작성할 때만 해도 STL을 거의 사용하지 않았을 때인지라 무식하게 배열을 사용했지만, STL의 map 자료형을 사용하면 더 쉽게 풀 수 있을거라고 보입니다.

 

Pythagoras Triangle

문제를 간단하게 요약하자면 다음과 같습니다.

 

변의 길이가 정수인 직각삼각형이 있습니다.  둘레 길이가 주어졌을 때, 어떤 정수 직각 삼각형은 여러개가 나올 수 있습니다.  L < 1,500,000 인 둘레길이를 가지면서, 해당 둘레에서 그러한 정수 직각삼각형이 오직 한개인 개수를 구하세요.

 

문제의 원본은 다음과 같습니다.

https://projecteuler.net/problem=75

Problem 75 - Project Euler

 

모든 정수 직각삼각형은 다음과 같은 공식으로 표현될 수 있습니다.

 

직각 삼각형의 세 변의 길이를 a, b, c라고 한다면, 양의 정수 m, n에 대하여

\[ a = \frac{m^2 - n^2}{2} \]

\[ b = mn \]

\[ c = \frac{m^2 + n^2}{2} \]

 

이 중, \( (m, n)=1 \)인 경우를 근원 정수 직각삼각형(primitive integral right triangle)이라고 합니다.

 

위의 공식을 이용하여 세변의 길이를 더하면, \( L = m^2 + mn \)이 됩니다.

 

이 문제에서는 세 변의 길이가 각각 필요한 것이 아니고, 전체 길이가 중요하기 때문에 이 길이를 이용합니다.

 

그런 후에 에라스토테네스의 체처럼 필요한 숫자들을 검사해주면 됩니다.

 

올바른 결과가 나오는지 검사하기 위해서 몇개의 값을 공유합니다.

 

L	Answer
100	11
500	59
1,000	112
5,000	556
10,000	1,120

 

아래는 제가 작성한 소스입니다.  참고용으로 봐주세요.

//--------------------------------------------------------------------
//  Project Euler #75 - Singular integer right triangles
//    - by Aubrey Choi
//    - created at 2015-10-07
//--------------------------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <time.h>

int gcd(int a,int b) { while(b) { int t=a%b; a=b; b=t; } return a; }
void solve1(int N)
{
  static int count[1500001];
  int ptcount = 0;

  for( int m = 3 ; m < 1224 ; m+=2 )
  {
    for( int n = 1 ; n < m ; n+=2 )
    {
      if( gcd(m, n) > 1 ) continue;
      int len = m*(m+n);
      if( len > N ) break;
      ptcount++;
      for(int i=1;len*i<=N;i++) count[i*len]++;
    }
  }

  printf("pytagoras primitive count which length is below and equal %d is %d\n", N, ptcount);

  int ans = 0;
  for(int len = 12 ; len <= N ; len+=2) if( count[len] == 1 ) ans++;
  printf("Ans = %d\n", ans);
}

int main()
{
  clock_t t;
  t = clock();
  int n; scanf("%d", &n);
  solve1(n);
  printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}