[백준 BOJ 1009번] 분산처리 (C / C++ ) [수학, 구현]

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	44560	10571	8310	25.229%

 

문제

재용이는 최신 컴퓨터 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)

 

출력

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

 

예제 입력 1

5
1 6
3 7
6 2
7 100
9 635

예제 출력 1

1
7
6
1
9

풀이

각 데이터는 a^b의 형태로 주어진 다는 것에 주목합니다. 데이터가 작을 때는 int형 데이터타입 내에서도 문제를 풀 수 있지만 9^635는 long long 데이터타입도 순식간에 벗어나서 문제를 해결할 수 없습니다.

그러기 위해서는 규칙을 찾아 문제를 간소화 하면 되는데 수를 제곱하다보면 맨 끝자리 수의 주기가 있다는 것을 알 수 있습니다.

각각 제곱을 해 보면 네 번 마다 끝자리 수가 다시 같아지는 주기를 확인할 수 있습니다.

그렇게 되면 100번을 제곱하나 1000번을 제곱하나 네 번마다 주기가 돌아오니 차라리 아무리 숫자가 커져봤자 최대 네번 까지만 제곱할 수 있게 mod를 해 주면 됩니다. 그 후 a를 b번만큼 제곱해 주면 됩니다.

출력을 할 때는 mod 10을 해서 끝자리 수를 출력해주면 되는데, 주의할 점은 10번 데이터는 10번 컴퓨터라고 출력하라고 되어 있으니 조건문을 사용하여 숫자가 10으로 나누어 떨어지면 0이 아닌 10이 출력될 수 있게 해줍니다.

코드

#include <iostream>
using namespace std;
int main() {
	int t,a,b, mul;
	cin >> t;
	while(t--) {
		mul = 1;
		cin >> a >> b;
		b=!(b%4)?4:b%4;
		while (b--)mul *= a;
		cout << (mul%10?mul%10:10) << "\n";
	}
}

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

1009번: 분산처리