백준 #1009 분산처리

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

 

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

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

 

 

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

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

 

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

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

 

그래도 숫자가 크지 않으니까 $a^{b}mod10$에 대해서 계산해보도록 하죠.  a = 3, b = 7 이라고 해보죠.

$$3^1=3(mod10)$$

$$3^2=9(mod10)$$

$$3^3=7(mod10)$$

$$3^4=1(mod10)$$

$$3^5=3(mod10)$$

$$3^6=9(mod10)$$

$$3^7=7(mod10)$$

 

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

$$2^1=2(mod10)$$

$$2^2=4(mod10)$$

$$2^3=8(mod10)$$

$$2^4=6(mod10)$$

$$2^5=2(mod10)$$

 

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

 

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

 

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

$$a^b=(amod10{)}^{bmod4}(mod10)$$

 

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

 

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

//----------------------------------------------------------------------------------
//  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;
}