[C/C++] 프로젝트 오일러 #110 Diophantine Reciprocals II(우선순위큐)

이 문제는 #108 문제와는 아주 비슷합니다.  

 

https://sdev.tistory.com/1968

[C/C++] 프로젝트 오일러 #108 Diophantine Reciprocals I(소인수분해)

 

요구하는 것도 비슷하지만, 문제 난이도는 #108이 30%로 책정되었지만, 이번 문제는 40%로 책정되어 있습니다.

 

다음과 같은 형태의 방정식을 고려합니다:

\[ \frac{1}{x} + \frac{1}{y} = \frac{1}{n} \]

여기서 x, y, n는 모두 양의 정수입니다.

이 방정식은 약간 변형된 형태로 나타낼 수도 있습니다:

\[ (x - n)(y - n) = n^2 \]

이 변형된 형태에서 x와 y는 n보다 큰 양의 정수입니다. n 값에 대해 가능한 (x, y)의 쌍을 찾는 것이 목표입니다.

문제의 목표는 특정 n에 대해 방정식을 만족하는 (x, y) 의 가능한 쌍의 개수를 최대한 작게 만드는 것입니다. n을 선택했을 때, 가능한 모든 (x, y) 의 쌍의 개수를 \(D(n)\)이라 한다면 \(D(n) > 4,000,000\)인 최소의 n을 구하는 것이 문제의 핵심입니다.

 

Diophantine equation

제가 작성한 소스입니다.  그러고 보니 우선순위큐를 직접 제작했네요.  그냥 라이브러리 쓰면 편한데.  

//------------------------------------------------
//    Project Euler #110 - Diophantine Reciprocals II
//        - by Aubrey Choi
//        - created at 2015-11-04
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    M    4000000
//#define    M    100

class PQueue
{
public:
    PQueue(int64_t *inodes, int icount) : nodes(inodes), total(icount), n(0) { }
    void Enqueue(int64_t v)
    {
        if( n >= total ) return;
        int last = n++;
        while( last >= 1 )
        {
            int p = (last-1)/2;
            if( nodes[p] < v ) break;
            nodes[last] = nodes[p];
            last = p;
        }
        nodes[last] = v;
    }
    int64_t Dequeue()
    {
        if( n == 0 ) return -1;
        int64_t ret = nodes[0];
        int last = 0;
        int64_t v = nodes[--n];
        while( last*2+1 < n )
        {
            int min = last*2+1;
            if( min+1 < n && nodes[min] > nodes[min+1] ) min++;
            if( nodes[min] > v ) break;
            nodes[last] = nodes[min];
            last = min;
        }
        nodes[last] = nodes[n];
        while( n > 0 && nodes[0] == ret ) Dequeue();
        return ret;
    }

private:
    int64_t *nodes;
    int n, total;
};

void solve1()
{
    int primes[20];
    int pcount = 0;

    primes[pcount++] = 2;
    primes[pcount++] = 3;
    for( int p = 5 ; pcount < 20 ; p+=2 )
    {
        bool isPrime = true;
        for( int i = 1 ; primes[i]*primes[i] <= p ; i++ )
        {
            if( p%primes[i] == 0 ) { isPrime = false; break; }
        }
        if( isPrime ) primes[pcount++] = p;
    }

    int64_t numbers[100000];
    PQueue queue(numbers, 100000);

    queue.Enqueue(2);

    while( true )
    {
        int64_t n = queue.Dequeue();
        int last = 0x7fffffff;
        int sigma = 1;
        for( int i = 0 ; i < 20 ; i++ )
        {
            int cnt = 0;
            for( uint64_t k = n ; k%primes[i] == 0 ; cnt++, k/=primes[i] ) ;
            if( last > cnt ) queue.Enqueue(n*primes[i]);
            last = cnt;
            if( cnt == 0 ) break;
            sigma *= 2*cnt+1;
        }
        if( (sigma+1)/2 > M )
        {
            printf("Ans = %jd (%d)\n", n, (sigma+1)/2);
            break;
        }
    }
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

 

(1) PQueue 클래스

• 목적: 최소 우선순위 큐를 구현하여 숫자를 효율적으로 정렬하고, 가장 작은 값을 빠르게 가져옵니다.
• 역할: n 후보를 관리하며, 현재 가장 작은 n 값을 먼저 처리합니다.

class PQueue
{
    ...
}

• Enqueue: 큐에 값을 삽입하고 정렬합니다.
• Dequeue: 큐에서 최소 값을 꺼내고, 다음 처리를 위한 후보 값을 생성합니다.

(2) 소수 생성

int primes[20];
primes[pcount++] = 2;
primes[pcount++] = 3;
for( int p = 5 ; pcount < 20 ; p+=2 )
{
    ...
}

• n 값을 소수의 거듭 제곱의 곱으로 표현하기 위해 첫 20개의 소수를 구합니다.
• n을 소수 \(  p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k} \)  형태로 분해하는 데 사용됩니다.

(3) 후보 n 생성 및 처리

queue.Enqueue(2);
while( true )
{
    int64_t n = queue.Dequeue();
    ...
}

• 초기 값으로 n = 2를 큐에 넣고 시작합니다.
• 큐에서 n 값을 꺼내어 다음 계산을 진행합니다.

(4) 약수 계산 및 조건 확인

int sigma = 1;
for( int i = 0 ; i < 20 ; i++ )
{
    int cnt = 0;
    for( uint64_t k = n ; k%primes[i] == 0 ; cnt++, k/=primes[i] ) ;
    ...
    sigma *= 2*cnt+1;
}

• n 의 소인수 분해를 통해 \( n^2 \)의 약수 개수를 계산합니다.
• \( n^2 \) 의 약수 개수는 \(  (2e_1+1)(2e_2+1)\ldots \) 로 표현됩니다. 

(5) 정답 조건 확인

if( (sigma+1)/2 > M )
{
    printf("Ans = %jd (%d)\n", n, (sigma+1)/2);
    break;
}

• \(  (sigma+1)/2 \)는 \( D(n) \)에 해당합니다.
• \(  D(n) > 4,000,000 \) 이면, 현재 n이 조건을 만족하는 가장 작은 값으로 출력하고 종료합니다.

(6) 큐에 다음 후보 추가

if( last > cnt ) queue.Enqueue(n*primes[i]);

• b의 새로운 후보를 n*primes[i] 형태로 생성하여 큐에 삽입합니다.
• 이 과정은 n 값의 증가를 제어하며, 최소 값을 찾는 데 도움을 줍니다.