문제 링크입니다: www.acmicpc.net/problem/1009
1009번: 분산처리
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
www.acmicpc.net
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를 적용한 뒤 마지막으로 처리될 컴퓨터의 번호를 구해주면 됩니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 21335번 Another Eruption (0) | 2021.04.02 |
|---|---|
| 백준 1247번 부호 (0) | 2021.03.31 |
| 백준 21185번 Some Sum (0) | 2021.03.30 |
| 백준 20976번 2 番目に大きい整数 (0) | 2021.03.30 |
| 백준 20673번 Covid-19 (0) | 2021.03.30 |