1629번 - 곱셈
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를 적절히 집어넣어주면 됩니다!!
헛 그렇네요 ㄷㄷ 그냥 prev만 기록해놔도 되는군요
댓글을 작성하려면 로그인해야 합니다.
ekdrn1 2년 전 1
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를 적절히 집어넣어주면 됩니다!!