프로젝트 오일러 #64 홀수 주기의 제곱근

프로젝트 오일러 #64 는 연분수로 제곱근을 표현하는 문제입니다.  문제의 난이도는 20%입니다.  알고리즘적으로 어려운 것보다는 수학적 개념의 어려움이 있었던 문제라고 봅니다.  제곱근을 연분수로 표현하는 문제는 #57번(http://sdev.tistory.com/237)에 이미 나왔었습니다.

 

문제의 링크는 아래와 같습니다.

https://projecteuler.net/problem=64

 

연분수로 표현할 때, 중요한 점은 분자는 항상 1이 되어야 한다는 것입니다.

예를 들어서 7의 제곱근인 \( sqrt{7} \)은 다음과 같이 표현할 수 있습니다.

 

\[ \sqrt{7} = 2 + \sqrt{7} - 2 \]

 

위 식은 너무나도 당연한 것이겠지만요.  우리는 이것을 이용해서 연분수를 만들 수가 있습니다.  일단 무리수를 정수부와 소수부로 위와 같이 나눕니다.  \( \sqrt{7} \) 의 경우에는 정수부가 2이므로, \( \sqrt{7} - 2 \) 는 소수부가 됩니다.  그런 후에 소수부를 역수로 만들면 자연스럽게 분자가 1인 분수가 만들어집니다.

 

\[ \sqrt{7} = 2 + \sqrt{7} - 2 = 2 + \frac{1}{ \frac{1}{\sqrt{7} - 2} } \]

 

그런후에 분모의 유리화를 합니다.

 

\[ \sqrt{7} = 2 + \sqrt{7} - 2 = 2 + \frac{1}{ 1+\frac{ \sqrt{7} -1} {3} } \]

 

이것을 계속 반복하면, 우리는 연분수로 원하는 제곱근을 표현할 수 있습니다.

이렇게 연분수로 표현하다 보면, 주기가 발생하는데, 이 주기가 홀수인 제곱근의 갯수를 주어진 범위안에서 세는 것이 문제입니다.

 

이 문제를 저는 단순하게 위의 연분수를 만드는 과정을 구현했습니다.  그렇게 해서 정수가 반복되어 나타나게 되고, 그 주기를 기록해서 단순하게 카운팅을 해서 답을 냈습니다.  더 좋은 방법이 있을지 아닐지 모르겠습니다.  답을 낼때까지 10ms 정도밖에 안 되서, 성능은 신경쓰지 않았네요.

 

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

//----------------------------------------------------------------------------------------
//  Project Euler #64 - Odd period square roots
//    - by Aubrey Choi
//    - created at 2015-04-02
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>

int GetPeriod(int n);
int main()
{
  int count = 0;
  for( int i = 2 ; i <= 10000 ; i++ )
  {
    int p = GetPeriod(i);
    if( p%2 ) count++;
  }
  printf("ans = %d\n", count);
}

int GetPeriod(int n)
{
  double r = sqrt(n);
  int s = r;
  if( s*s == n ) return 0;
  int q = 1;
  int count = 0;
  do
  {
    q = (n-s*s)/q;
    int t = (r+s)/q;
    s = t*q - s;
    count++;
  } while( q != 1 );
  return count;
}