프로젝트 오일러 #44 오각수

이번 문제는 오각수라는 특이한 수를 만들어내어야 합니다.

 

오각수는 오각형으로 점을 찍어나갈 때, 점의 갯수입니다.  편의를 위해서 그림을 첨부하면 다음과 같습니다.

 

 

프로젝트 오일러 사이트의 문제는 다음과 같습니다.

오각수라는 것을 설명하고 있고, 오각수들의 순열중에, 어느 두개의 오각수의 차와 합이 또다른 오각수들이 되는 것을 찾아야 합니다.

 

 

오각수를 나타내는 공식은 문제에서와 같이 다음과 같습니다.

 

\[ P_n = n(3n-1)/2 \]

 

그리고 오각수는 단순증가이므로, 결국 문제에서 원하는 것은 다음을 만족하는 최소의 \(P_s\) 값을 찾는 것입니다.

 

\[ P_s + P_t = P_u \]

\[ P_t + P_u = P_v \]

 

그냥 단순한 방법으로 위 식을 만족하는 s, t 를 찾으면 됩니다.

저는 조금 복잡하게 풀어보았습니다.

 

아래는 이것을 구현한 소스입니다.  참고만 해주세요.

 

#include <stdio.h>
#include <stdint.h>
#include <math.h>

int main()
{
    for( int64_t i = 2 ; ; i++ )
    {
        int64_t s = i*(3*i-1)/2;

        for( int64_t k = 1 ; k < i ; k++ )
        {
            int64_t t = s - k*(3*k-1)/2;
            if( t%(3*k) ) continue;
            int64_t c1 = t/(3*k);
            int64_t c2 = c1+k;
            int64_t t1 = c1*(3*c1-1)/2;
            int64_t m = (6*c2-1)*(6*c2-1)+24*t1;
            int64_t c = sqrt((double)m);
            if( c*c != m && (c+1)*(c+1) != m ) continue;
            c -= 6*c2-1;
            if( c <= 0 || c%6 ) continue;
            printf("ans = %jd\n", s);
            return 0;
        }
    }
}