목록거듭제곱 (1)

1일1알

백준 10830번 행렬 제곱 C++

a^b에서 b가 홀수라면 b를 1 빼주고 결과(처음에는 단위행렬)에 a를 곱해주고 b가 짝수라면 a^b = (a^2)^(b/2) 이기 때문에 a를 제곱해주고 b를 2로 나눠주었다. 2^7를 예로 들자면 우선 처음에 결과는 1로 시작한다. (res = 1) 2^7 에서 7이 홀수이기 때문에 2^6 으로 바꾸고 res에 2를 곱한다 (res = 2) 2^6 에서 6이 짝수이기 때문에 4^3으로 바꿔준다. 4^3에서 3이 홀수이기 때문에 4^2로 바꿔주고 res에 4를 곱한다(res = 8) 4^2에서 2가 짝수이기 때문에 16^1로 바꿔준다. 16^1에서 1이 홀수이기 때문에 16^0으로 바꿔주고 res에 16을 곱한다(res = 128) b가 0이 됐기 때문에 그만 계산한다. 2^7 = res = 128이..
알고리즘 2022. 6. 29. 11:08
이전 Prev 1 Next 다음