백준 1009번 분산처리

문제 링크입니다: www.acmicpc.net/problem/1009

1009번: 분산처리

b가 최대 백만이기 때문에 a^b를 계산하기보다는 다른 방법을 찾아야하는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. a 제곱을 거듭하며 일의 자리가 반복되는 사이클의 길이를 구합니다. (getCycleCnt 메서드)

2. 결국 일의 자리는 반복되기 때문에 a^b를 해주는 대신 a^(b%cycleCnt)를 해주면 됩니다.

-> 여기서 b%cycleCnt가 0일 경우 cycleCnt번 제곱해줘야합니다.

2.1 컴퓨터의 번호가 1 ~ 10이기 때문에 결국 일의 자리 숫자가 중요합니다. 제곱을 해주면서 오버플로우를 방지하기 위해 a에 일의 자리수만 저장하면서 반복문을 진행해주면 됩니다.

3. a=20, b=1과 같은 케이스를 고려하여 반복문 이후에도 a %= MAX를 적용한 뒤 마지막으로 처리될 컴퓨터의 번호를 구해주면 됩니다.

	#include <iostream>
	using namespace std;
	const int MAX = 10;
	int getCycleCnt(int a)
	{
	bool visited[MAX] = { false, };
	int cnt = 1;
	visited[a % MAX] = true;
	int copyA = a;
	while (true)
	{
	a *= copyA;
	a %= MAX;
	if (visited[a])
	{
	break;
	}
	cnt++;
	}
	return cnt;
	}
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
	int a, b;
	cin >> a >> b;
	int copyA = a;
	int cycleCnt = getCycleCnt(a);
	int powCnt = (b % cycleCnt) == 0 ? cycleCnt : (b % cycleCnt);
	for (int i = 1; i < powCnt; i++)
	{
	a *= copyA;
	a %= MAX;
	}
	a %= MAX;
	cout << (a == 0 ? 10 : a) << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~