ekdrn1   2년 전

DP 배열 사이즈: 64개

DP 배열 인덱스: 지수가 2의 거듭제곱일 때의 결과

인덱스 찾는법: 비트 연산자 활용

arr64[0] = A^(2^0) = A

arr64[1] = A^(2^1) = A^2 = arr64[1-1] * arr64[1-1]

arr64[2] = A^(2^2) = A^4 = arr64[2-1] * arr64[2-1]

...

지수 B는 메모리 내에 이진법으로 저장되어 있습니다.

예를 들어 B가 7이면

B == 2^0 + 2^1 + 2^2 == 111(2) == 1<<0 + 1<<1 + 1<<2

-> A^7 == A^(1<<0 + 1<<1 + 1<<2) == arr64[0] * arr64[1] * arr64[2]

여기에 mod를 적절히 집어넣어주면 됩니다!!

zenith82114   2년 전

여기서 생각을 조금 더 해보시면 배열마저도 필요가 없다는 것을 아실 수 있습니다.

ekdrn1   2년 전

헛 그렇네요 ㄷㄷ 그냥 prev만 기록해놔도 되는군요

댓글을 작성하려면 로그인해야 합니다.