Creative Commons License
Creative Commons License

#69 문제와 비슷하게 이 문제도 오일러의 수를 다루고 있습니다.


난이도는 20%이네요.



문제 자체는 해석하는 데 있어서 어려움이 없습니다.


n에 대한 오일러의 수가, n과 자릿수도 같고, 숫자의 조합도 같다면, 그 수는 순열수라고 할 수 있습니다.


이러한 순열수가 되는 10억 미만의 n 중에 그 비율이 최소가 되는, (즉, 상대적으로 오일러의 수가 크게 나오는) n을 찾으라는 것입니다.


이 문제를 #69와 같이 풀 수도 있겠지만요.  순열수가 되어야 한다는 조건 때문에, 일단 무식하게 프로그램을 짜보았습니다.


아쉽게도 무식하게 프로그램을 작성하면 시간이 많이 걸립니다.  전 12초정도 시간이 걸리네요.


순열수인지 아닌지는 9로 나눈 나머지가 동일한지 검사했습니다.  일단 그렇게 하면 많은 경우의 수가 줄어듭니다.  예를 들어서 소수는 100% 이 검사로 순열수가 아님을 알 수 있습니다.  n이 20이라면, 오일러의 수는 8입니다.  9로 나눈 나머지는 각각 2와 8로 순열수가 될 수 없음을 알 수 있습니다.  (이 원리를 이용해서 애시당초 오일러의 수를 구하지 않을 수도 있을겁니다.)


더 좋은 알고리즘을 찾을 수 있었겠지만, 여기서는 그렇게 하지 않았습니다.


제가 짠 소스코드는 다음과 같습니다.



#include <stdio.h>
#include <time.h>

int primes[10000];
int pcount = 0;

int phi(int n)
{
    int v = 1;
    for( int i = 0 ; n > 1 && i < pcount ; i++ )
    {
        if( n%primes[i] == 0 )
        {
            v *= primes[i]-1;
            n /= primes[i];
            while( n%primes[i] == 0 ) { v *= primes[i]; n /= primes[i]; }
        }
    }
    if( n > 1 ) v *= (n-1);
    return v;
}

void solve1()
{
    primes[pcount++] = 2;
    primes[pcount++] = 3;
    primes[pcount++] = 5;
    primes[pcount++] = 7;
    for( int p = 11 ; p < 10000 ; 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;
    }

    double minv = 1000.0;
    int minn = 0;
    for( int n = 3 ; n < 10000000 ; n += 2 )
    {
        int v = phi(n);
        if( (n%9) != (v%9) ) continue;
        int m[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int cn = n, cv = v;
        while( cn ) { m[cn%10]++; cn/=10; }
        while( cv ) { m[cv%10]--; cv/=10; }
        bool isPerm = true;
        for( int i = 0 ; i < 10 ; i++ )
            if( m[i] ) { isPerm = false; break; }
        if( isPerm )
        {
            double s = (double)n/v;
            if( s < minv ) { minv = s; minn = n; }
        }
    }
    printf("Ans = %d\n", minn);
}


저작자 표시 비영리 변경 금지
신고



Creative Commons License
Creative Commons License

이번 문제는 난이도 10%의 문제입니다.


사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다.


오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다.  이 수는 암호학 등에서 아주 중요하게 다루어집니다.  RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다.


대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠.  (요즘은 중학생들도 이것을 아는 애들이 있습니다.  수학 올림피아드에서 가끔씩 나오는 문제이다보니.  제 경우에는 정수론 책을 하나 사서 독학을 했습니다.)



문제에서는 n에 대하여 오일러의 수 비율이 최대가 되는 수를 찾는 것입니다.  1,000,000이라는 숫자 한계가 있습니다.


오일러의 수는 약수의 갯수를 구하는 로직과 크게 차이는 없습니다.  약간의 변형이 필요하지만, 약수의 갯수를 구하는 로직과 비슷합니다.


실제 오일러의 수를 구하는 식은 다음과 같이 표현할 수 있습니다.


식이 좀 복잡해보이겠지만, n을 나누는 모든 소수 p에 대하여, n이 p라는 소인수를 d개 가지고 있다면, (p-1)에, p의 d-1승을 계속 곱하면 그것이 오일러의 수라는 것입니다.


이것을 C++ 로 프로그램하면 다음과 같습니다.


int phi(int n)
{
    int v = 1;
    for( int i = 0 ; n > 1 && i < pcount ; i++ )
    {
        if( n%primes[i] == 0 )
        {
            v *= primes[i]-1;
            n /= primes[i];
            while( n%primes[i] == 0 ) { v *= primes[i]; n /= primes[i]; }
        }
    }
    if( n > 1 ) v *= (n-1);
    return v;
}


위의 함수를 이용해서 풀어도 이 문제를 풀 수는 있습니다.  그런데 저는 좀 다르게 했습니다.  어차피 소수를 구하는 것, 모든 소수에 대하여 기존에 구해진 오일러의 수 값을 가지고 최대값을 구하는 방식으로 하였습니다.


성능 테스트는 따로 하지 않았습니다.  하지만 아무래도 연산 오더의 차이가 있으니까요.  좀 더 나을려나요.


아래는 실제 제가 이 문제를 해결할 때 사용한 프로그램입니다.


#include <stdio.h>
#include <time.h>

int maxvalues(int primes[], int pcount, int k, int n, int phi, int *maxp)
{
    int maxv = n, maxphi = phi;
    for( int i = k ; i < pcount ; i++ )
    {
        if( n*primes[i] > 1000000 ) break;
        int u = 0;
        int c = maxvalues(primes, pcount, i+1, n*primes[i], phi*(primes[i]-1), &u);
        if( (double)c/u > (double)maxv/maxphi ) { maxv = c; maxphi = u; }
    }
    *maxp = maxphi;
    return maxv;
}

void solve1()
{
    static int primes[1000];
    int pcount = 0;
    int n = 2;

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

    int maxp;
    n = maxvalues(primes, pcount, 0, 2, 1, &maxp);

    printf("Ans = %d\n", n);
}




저작자 표시 비영리 변경 금지
신고



Creative Commons License
Creative Commons License

프로젝트 오일러 #152를 풀면서 몇가지 새롭게 구현했던 것들이 많았네요.


기본적으로 모든 조합을 찾기 위해서는 O(2^n)인 탓에, 35, 45개일 때는 그나마 적정한 시간에 구할 수 있었지만, 80개에서는 그것이 안 되었네요.


이럴 때, 경우의 수를 줄여주는 것이 필요한데, 어떤 식으로 경우의 수를 줄일 것인지 고민을 많이 했네요.  더더구나 문제가 3의 배수는 총 26개나 나온다는 것이었죠.


처음에는 그룹을 지어서 할 생각이었는데.. 그룹을 지으면 전혀 안 되는 문제라는 사실을 조금 고민하면서 알게 되었네요.   회사에 있으면서도 어떻게 풀까 고민했었는데..  결국 경우의 수를 줄이는 방법을 생각했고, 제 구닥다리 노트북에서도 0.1초에 답을 내었네요.


여러가지 연산시간을 줄이는 방법도 생각을 했었는데.. 예를 들어서 x란 숫자가 2의 n승인지 아닌지를 판단하는 방법..


일반적으로는

bool is2pow = false;

for( int i = 0 ; i < 31 ; i++ )

  if( x == (1<<i) ) { is2pow = true; break; }

형태로 짜야할텐데, 이렇게 하면, 평균적인 시간이 많이 들겠더라고요.


그래서 고민했던 것이..

bool is2pow = ((x&-x) == x);

였네요. 


그리고 실제 제가 필요한 것은 2의 홀수승이었는데..

2의 n제곱인 것만으로는 알 수 없으므로... 비트 검사를 또 했네요.


x & 0x5555555...55


사실 계산하려면.. ((unsigned)-1)/3 으로 위의 0x5555...55 숫자를 얻을 수 있겠죠.


여하튼 #152 풀기 위해서 고민 많이 했었는데, 몇가지 실수를 해서 헤매긴 했지만 재밌게 풀었네요.




저작자 표시 비영리 변경 금지
신고

티스토리 툴바