[C/C++] 프로젝트 오일러 #508 : \(i-1\) 진법 표시하기(수학)

이번 문제는 아직까지도 푼 사람이 100명이 넘지 않는 문제네요.

 

그만큼 복잡할 수 있는 문제이므로, 블로그에 자세한 풀이법을 적기는 힘드네요.

 

문제는 주어진 범위안의 복소수를 \(i-1\) 진법으로 표현했을 때, 1의 갯수의 총 합입니다.

 

복소수에 보면, 정수가 계수인 복소수들이 자연수의 소수처럼 취급될 수 있는 것들이 있습니다.  이것들을 일반적으로 가우스 소수라고 합니다.  가우스 소수는 몇가지 법칙이 있는데요.  기본적으로 자연수의 소수에서 갈라지게 됩니다.

 

자연수의 소수 중 \(4k+3\) 형태의 소수는 자체로 가우스 소수가 됩니다.  즉, 3, 7, 11, 19, .. 등입니다.

그 외의 자연수 소수들은 모두 복소수 형태의 가우스 소수로 나누어지게 됩니다.  예를 들어서 소수 2는 \( \pm 1 \pm i \)의 4가지 가우스 소수를 가집니다.  소수 5는 \( \pm 2 \pm i , ~ \pm 1 \pm 2i \) 형태로 8가지의 가우스 소수로 나타낼 수 있습니다.  이는  \( a^2 + b^2 \)이 홀수 소수가 되는 경우 \( 4k+1 \) 형태가 되기 때문입니다.  짝수 소수인 2는 a = 1, b = 1인 경우가 되겠죠.

 

뭐 이 문제를 풀기 위해서 위의 이론을 잘 알아야 할 필요는 없습니다.

 

주어진 문제의 크기가 10의 15승 오더이고, 음수와 허수부까지 모두 친다면, 단순 무식한 방법으로 주어진 문제를 풀기 위해서는 \( 4 \times 10^{30} \) 정도의 계산을 해야 합니다.

 

그 계산을 위해서는 다음과 같은 함수가 필요하겠죠.

 

uint64_t GetGaussianInteger(int64_t r, int64_t i)
{
    gcount++;
    uint64_t count = 0;

    while(r || i)
    {
        if( (r^i)&1 ) { r--; count++; }
        int64_t x = (i-r)/2;
        i = -(i+r)/2;
        r = x;
    }

    return count;
}

int GetGaussianInteger(int64_t r, int64_t i, char s[])
{
    int n = 0;

    do
    {
        if( (r^i)&1 ) { r--; s[n++] = '1'; }
        else { s[n++] = '0'; }
        int64_t x = (i-r)/2;
        i = -(i+r)/2;
        r = x;
    }
    while(r || i);

    return n;
}

실수부와 허수부가 (짝수, 홀수)이거나 (홀수, 짝수)인 경우에는 \( d_k \)가 1이 됩니다.  그 외의 경우에는 0이 되고요.

 

이 함수 자체에도 모든 자릿수가 나오기 위해서는 여러번의 반복문이 실행됩니다.  그래서 단순 무식 방법으로는 이 문제를 절대 풀 수가 없습니다.  예제로 나왔던 500이라면 충분하게 풉니다.

 

그래서 사이즈를 줄여나가는 방법을 써야 합니다.

제 경우에는 2m x 2n 크기의 공간을 m x n 크기의 공간으로 줄이는 방법을 사용했습니다.  그러니 전체적으로 보면, 아무리 큰 크기의 문제라도 실제 연산시간은 대폭 줄어듭니다.  참고로 저는 답을 내는데 18ms 걸렸습니다.

 

10의 10승인 경우에는 다음과 같은 답이 나옵니다.  참고하시길 바랍니다.

\( B(10^{10}) = 396,433,725 \)