백준 #1009 분산처리

분산처리 문제는 무식하게 풀려면 얼마든지 풀 수 있지만, 효율적인 동작을 위해서는 정수론이 필요합니다.

 

문제 자체는 이해 자체가 어렵지는 않습니다.

데이터가 N개 있는데, 10대의 컴퓨터로 순차적으로 데이터 1개씩을 처리할 경우, 마지막 데이터를 처리하는 컴퓨터는 어떤 것이 될 것인가가 문제입니다.

 

 

아래는 이 문제의 링크입니다.

https://www.acmicpc.net/problem/1009

 

그런데 여기서 주어진 N이란 숫자가 두개의 숫자 a, b 가 주어졌을 때, \(a^b\)이란 것입니다.

더구나 a 의 범위는 100까지이고, b란 범위는 1,000,000 까지입니다.  나머지 연산을 할 경우, 밑수를 나머지 연산을 할 수 있지만, 지수를 나머지 연산하는 것은 중학 수학 범위에서는 벗어납니다.

 

그래도 숫자가 크지 않으니까 \(a^b ~ mod ~ 10\)에 대해서 계산해보도록 하죠.  a = 3, b = 7 이라고 해보죠.

\[ 3^1 = 3 (mod ~10)\]

\[ 3^2 = 9 (mod ~10)\]

\[ 3^3 = 7 (mod ~10)\]

\[ 3^4 = 1 (mod ~10)\]

\[ 3^5 = 3 (mod ~10)\]

\[ 3^6 = 9 (mod ~10)\]

\[ 3^7 = 7 (mod ~10)\]

 

계산을 해보면, 순환을 하는 모습을 볼 수 있습니다.  이번에는 a = 2, b = 5 라고 해볼께요.

\[ 2^1 = 2 (mod ~10)\]

\[ 2^2 = 4 (mod ~10)\]

\[ 2^3 = 8 (mod ~10)\]

\[ 2^4 = 6 (mod ~10)\]

\[ 2^5 = 2 (mod ~10)\]

 

두개의 계산을 해보면, \( a^5 = a^1 (mod ~ 10) \) 이 되는 것을 볼 수 있습니다.  사실 이것만으로는 확실하다고 볼 수는 없습니다.  그렇다고 모든 a 에 대해서 다 해볼 수는 없고요.  (프로그램 돌려서 확인해보면 됩니다.)

 

\( a^b ~ mod ~10 = (a ~ mod ~ 10)^b ~ mod ~10 \)으로 바꾸어도 되기 때문에 실제 필요한 a는 10까지만 해보면 됩니다.  그리고 싸이클이 생기는지 여부는 각 숫자별로 싸이클이 생기는 숫자의 최댓값을 기록해보면 알 수 있습니다.

 

정수론을 조금 공부해보았다면, 오일러의 수 \(\varphi(n)\)을 구하면 된다는 것을 알게됩니다.  제 경우에는 오일러의 수를 이용해서 구했습니다.  10은 \(2 \cdot 5\)이기 때문에 이것에 따라서 오일러의 수(Euler's totient)는 4라는 것을 구할 수 있습니다.  주기성을 4를 가지기 때문에 다음 식이 성립합니다.

\[ a^b = (a~mod~10)^{b~mod~4} (mod ~10) \]

 

이것을 이용하면 쉽게 이 문제를 풀 수 있습니다.

 

아래는 제가 짠 소스입니다.  참고용으로 봐주세요.

//----------------------------------------------------------------------------------
//  baekjoon #1009
//    - by Aubrey Choi
//    - created at 2019-09-08
//----------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
  int t, a, b, c;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%d%d", &a, &b); c=1; a%=10; b=(b+3)%4+1;
    while(b--) c*=a;
    printf("%d\n", (c+9)%10+1);
  }
  return 0;
}