[Baekjoon - 3189] tomo

난이도: Silver IV

 

태그

• Number Theory
• Simulation
• Pegionhole Principle

 

풀이

1. 필요한 부분만 남기면서 계산할 수 있을까?

예를 들면, \( A = 7, B = 13, C = 1327 \)이었다고 합시다.

그럼, '=' 버튼을 누를 때마다 나오는 값은 \( 7 \times 13 = 91, 91 \times 13 = 1\,183, 1\,183 \times 13 = 15\,379, 15\,379 \times 13 = 199\,927, \ldots \)가 됩니다.

\( B \)가 계속 곱해지는 형태니, 지수적으로 증가하게 될테고, 이는 계산이 오래 걸린다는 것을 의미하겠죠.

 

하지만 이 모든 값이 다 필요할까요?

저희가 필요한 건 결국 이 값의 Suffix가 \( C \)가 동일한지이기 때문에, \( C \)와 동일한 자릿수만 남기면서 계산하는 걸 생각해볼 수 있습니다.

 

근데 Suffix의 길이는 어떻게 \( C \)와 동일하게 할까요?

적당한 \( 10 \)의 제곱수로 나눈 나머지를 들고 있으면 됩니다.

// 예를 들면, \( 72999197351 \)의 마지막 \( 4 \)자리 수는, \( 72999197351 \text{ mod } 10^4 = 7\,351 \)이 되죠.

 

그러니, \( C \)의 길이와 동일하게 해주는 \( 10 \)의 제곱수를 계산한 뒤, 이 값으로 mod를 매 계산마다 해주면 됩니다.

 

2. \( C \)가 등장할 때와, NIKAD의 판정

\( C \)가 등장할 때를 판정하는 건 어렵지 않습니다.

[1]에서 이미 적당한 값으로 mod해주고 있으니, 계산 결과 == \( C \)만 해주면 되죠.

그러니까, \( i = 1 \)부터 시작해서, \( A \times B^i \text{ mod } 10^k = C \)를 만족시키는 첫 \( i \)를 찾은 순간 출력하면 됩니다.

 

문제는 NIKAD입니다. 영원히 등장하지 않는다는 건 어떻게 판별할까요?

 

어느 순간에 계산 결과가 \( R \)이었다면, 다음 계산 결과는 항상 \( BR \)이 됩니다.

만약 어떤 \( R \)을 2번 봤다면, 그 뒤로도 똑같은 경로를 타게 되고, 무한 루프를 돌게 되겠죠.

그러니, 어떤 수를 2번 보게 된 순간 NIKAD를 출력하면 됩니다.

 

하지만 정수의 개수는 무한합니다. 그러니, 적당한 순서를 따르면 영원히 새로운 값을 찾아낼 수도 있지 않을까요?

다행히도, 정수의 개수는 무한하지만, 이를 N으로 나눈 나머지의 개수는 유한합니다.

 

유한한 곳에서 무한히 많이 탐색한다면, 비둘기집의 원리에 의해 어떤 위치를 2번 이상 방문하게 되겠죠.

사실 무한히 많이 탐색할 필요도 없습니다. 종류가 \( N \)가지였다면, \( N+1 \)번 계산하는 순간 중복이 발생하겠죠.

 

\( C \)의 제한 때문에 mod의 값이 \( 10^6 \)을 넘어가지 않으니 충분히 빠른 AC를 기대해볼 수 있습니다.

// \( 10^5 \)이 아닙니다! \( C = 10^5 \)라면, 이를 제대로 판별하기 위해 \( 10^6 \)을 써야 하기 때문이죠.

 

3. 코드

bool chk[1000020];
 
void Main(){
    int a, b, c; cin >> a >> b >> c;
    int m = 10; while (c >= m){ m *= 10; }
    a = a*b % m;
    for (int ans = 1; !chk[a]; ans++){
        chk[a] = 1; if (a == c){ cout << ans; return; }
        a = a*b % m;
    }
    cout << "NIKAD";
}