52. 프로젝트 오일러 #52 : 순열 곱

52번 문제는 너무나도 유명한 문제여서, 문제를 보고서 프로그램 작성을 하지 않고도 답을 낼 수 있었습니다.

이 문제는 순환소수 중, 소수에 의한 문제입니다.

문제 자체는 어렵지 않으니까, 어떻게든 풀면 됩니다.  난이도 5% 문제입니다.  51번 문제가 난이도 15%로 잠깐 높아졌었지만요.

프로젝트 오일러 사이트의 문제는 다음과 같습니다.

125874와 같은 숫자는 2배를 하면 251748로 숫자의 위치만 바뀌어서 나타납니다.  x, 2x, 3x, 4x, 5x, 6x 가 모두 같은 숫자들을 가지고 있는 가장 작은 숫자를 찾으세요.

이 문제를 단순무식법으로 풀려면, 자릿수의 숫자만 계산해서 같은 숫자가 나오는지 검사하면 됩니다.  그렇지만, 그렇게 하면 시간이 많이 걸립니다.  사실 요즘 컴퓨터에서는 이렇게 하여도 순식간에 문제를 풀 수 있습니다.

그렇지만, 보다 쉽게 풀려면, 1/7을 계산하면 됩니다.  일단, 10 이 mod 7 의 원시근인지가 중요합니다.  그 이유는 순환마디의 수가 6자리가 될 수 있는 가 아닌가입니다.  예를 들어서 1/3 은 3의 오일러 수가 2임에도 불구하고, 10은 mod 3의 원시근이 아닙니다.  10 mod 3 = 1 로 원시근이 아니죠.  076923076923 이라는 12자리수는 1/13으로 만들어지는 수입니다. 이 수도 위와 같은 조건을 만족함을 알 수 있습니다.  아쉽게도 앞에 0이 들어가는 것은 어쩔 수 없습니다. 153846153846 는 위 수를 2배해서 얻어진 수입니다.  이 수 역시 위의 조건을 만족함을 알 수 있습니다.

조금 더 수학적으로 보시려면, 제 글 중 http://sdev.tistory.com/189 을 참조하세요.

10 mod 7 = 3 이고, 3은 7의 원시근입니다.  그렇기 때문에 1/7로 만들어지는 142857은 위의 문제에 딱 맞는 숫자입니다.  그러나 이 숫자는 순열수이긴 하지만, 6개의 자릿수가 순환하는 수입니다.  원래 문제보다 더 작은 집합에 속해있는 수입니다.

그래서 단순 무식법으로 문제를 확인차 풀어보았습니다.

#include <stdio.h>
#include <memory.h>

bool IsSameOrder(int a, int b, int digit);
int main()
{
    for( int digit = 2 ; digit < 8 ; digit++ )
    {
        int m = 1;
        for( int i = 1 ; i < digit ; i++, m *= 10 );
        for( int i = m ; i < m*10/2 ; i++ )
        {
            int k;
            for( k = 2 ; k <= 6 && IsSameOrder(i, k*i, digit) ; k++ );
            if( k > 6 )
            {
                printf("ans = %d\n", i);
                return 0;
            }
        }
    }
}

bool IsSameOrder(int a, int b, int digit)
{
    char check[2][10];
    memset(check, 0, sizeof(check));
    int s = 1;
    for( int i = 0 ; i < digit ; i++, s*=10 )
    {
        check[0][(a/s)%10]++;
        check[1][(b/s)%10]++;
    }
    return memcmp(check[0], check[1], 10) == 0;
}