[C/C++] 프로젝트 오일러 #26 : 순환고리

이번 문제는 가장 긴 순환고리를 찾는 문제입니다.  사실 순환고리는 오일러의 수 문제로 귀결됩니다.  오일러수는 다음과 같은 형태로 정의해서 낼 수 있습니다.

\[ n = \prod_{p_k \mid n} p_k^{a_k} \]
라고 한다면,  오일러의 수는

\[ \phi(n) = \prod_{p_k \mid n} (p - 1)p^{a_k - 1} \]
이라고 할 수 있습니다.

즉, n이 합성수라고 한다면, 오일러의 수는 엄청나게 줄어들게 됩니다.  n이 소수라면 n-1 이 오일러의 수가 됩니다.

가장 긴 순환고리를 찾기 위해서는 사실 오일러의 수만 가지고 판단할 수는 없습니다.  10이란 숫자를 가지고 10이 n의 원시근이면 오일러의 수와 동일한 순환고리를 가지겠지만, 원시근이 아니라면, 오일러의 수의 약수 중 하나의 순환고리를 갖습니다.

일단 2의 배수와 5의 배수는 비순환고리를 가짐으로 실제 검사할 숫자들은 \( 10k + 1, 3, 7, 9 \) 입니다.  이 숫자 이외에는 비순환고리를 만듭니다.

예를 들어서 600의 순환고리의 길이가 k라면 300의 순환고리의 길이 역시 k입니다.  2와 5는 10의 약수이기 때문에 600의 순환고리의 길이와 3의 순환고리의 길이는 동일합니다.  즉, 짝수로 끝나는 수와 5로 끝나는 수는 검사할 필요가 없는 셈이죠.

사실 1000 미만인 수에서 순환고리의 길이 다 계산한다고 얼마나 느려질까요.  하지만 그 숫자가 늘어난다면요.  10개중 4개만 검사하는 것이 더 빠르겠죠.  그리고 비순환고리의 경우를 생각할 필요가 없으니까요.

그리고 두번째로 속도를 개선하기 위해서, 뒤 숫자부터 차례대로 계산을 해서 현재 계산된 최대 순환고리의 갯수가 검사하고자 하는 수보다 커지면 프로그램을 종료하게 하였습니다.

 

reciprocal cycles

제시된 프로그램은 참고용으로만 보세요.

//------------------------------------------------
//    Project Euler #26 - Reciprocal Cycles
//        - by Aubrey Choi
//        - created at 2015-01-26
//------------------------------------------------
#include <stdio.h>

int main()
{
    int f[4] = { 1, 3, 7, 9 };
    int max = 6, v = 7;

    for( int i = 1000 ; i >= 10 ; i -= 10 )
    {
        if( i <= max ) break;
        for( int j = 0 ; j < 4 ; j++ )
        {
            int c = i-f[j];
            int k;
            int t = 10;
            for( k = 1 ; t != 1 ; k++ )
            {
                t = (t*10)%c;
            }
            if( k > max ) { max = k; v = c; }
        }
    }

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

 

이 프로그램은 1을 나눌 때 1000 미만의 수 중에서 가장 긴 순환 소수를 가지는 수를 계산합니다. 효율성을 높이기 위해 특정 최적화를 사용합니다. 프로그램이 동작하는 과정을 단계별로 설명하면 다음과 같습니다:

1. 초기화:
• 배열 f[4] = {1, 3, 7, 9}는  10k + 1, 3, 7, 9  형태의 숫자(2나 5로 나누어지지 않는 숫자)를 나타냅니다.
• 변수 max와 v는 최대 순환고리 길이와 해당 숫자를 저장하며, 초기값은 max = 6, v = 7입니다.

 

2. 바깥 루프:
• 1000에서 시작하여 10씩 감소하며 검사합니다 (10의 배수에 해당하는 숫자만 검사).
• 현재 숫자 i가 최대 순환고리 길이(max)보다 작거나 같으면 루프를 조기에 종료합니다.

 

3. 안쪽 루프:
• 유효한 숫자 f[j]를 i에서 뺀 후보 숫자 c를 계산합니다.
• k (순환고리 길이)와 t (나머지 계산용)를 초기화합니다.

 

4. 순환고리 길이 계산:
• 모듈러 연산을 사용하여  1/c 의 순환고리 길이  k 를 계산합니다.
• 나머지 t가 1로 돌아올 때까지  t = (t \times 10) \% c 를 반복합니다.

 

5. 최대 순환고리 업데이트:
• 계산된 순환고리 길이 k가 현재 최대값(max)보다 크면, max와 v를 새로운 순환고리 길이와 해당 숫자로 업데이트합니다.

 

6. 결과 출력:
• 결과로 숫자 v와 순환고리 길이 max를 출력합니다.