프로젝트 오일러 #70 오일러의 수 순열

#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);
}