[C++]백준 - 1009번 문제

1009번: 분산처리 (acmicpc.net)

1009번: 분산처리

 

1009번 : 분산처리

---

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

 

입력

---

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

 

 

출력

---

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

 

 

---

 

생각해 볼 점

---

요약하자면, a ^ b를 10으로 나눈 나머지를 출력하면 될 것 같습니다.

 

하지만, 나머지가 0일 경우에는 10번 컴퓨터가 출력하기 때문에 나머지가 0이라면 10으로 출력해주어야 합니다.

 

a ^ b는 손쉽게 컴퓨터 변수가 표현가능한 int 혹은 long long의 범위를 넘어가기 때문에, 나머지 정리를 이용하는 것이 좋습니다.

 

* 나머지 정리

 

A * X를 B로 나눈 나머지는

A를 B로 나눈 나머지에 X를 곱하여 B의 나머지를 구한 것과 동일하다.

 

즉, (A * X) % B == ((A % B) * X) % B 이다.

 

예를 들어,

 

- 7를 4로 나눈 나머지는 3입니다.

 

- 7 * 7을 4로 나눈 나머지는 1입니다.

 

그리고, 그것은 3 * 7을 4로 나눈 나머지와 같습니다.

 

- 7 * 7 * 7을 4로 나눈 나머지는 3입니다.

 

그리고, 그것은 1 * 7을 4로 나눈 나머지와 같습니다.

 

 

따라서, 위의 나머지 정리를 이용해 반복문을 돌려서 곱하면, 나머지를 구할 수 있습니다.

 

코드

---

#include <iostream>
using namespace std;

int main() 
{
    int TC;
    scanf("%d", &TC);
    
    for(int t = 0; t < TC; t++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        int result = 1;
        do
        {
            result = (result *a) % 10;
            b--;
        }while(b);
        if(result == 0) result = 10;
        printf("%d\n", result);
    }
    
	return 0;
}

 

그 외

---