백준 1629번 - 모듈러 연산과 지수 법칙

1629번 문제 풀다 배운 점을 정리한 글이다.

BOJ 1629번

혼자 문제 푸는데 실패해 다른 풀이를 참고해서 풀었다.
그 과정에서 모듈러 연산과 지수 법칙 응용에 대해 공부할 수 있었다.

지수 법칙

1067번의 문제의 경우 지수에 큰 값이 들어올 수 있다.
이때 지수의 법칙을 응용한 재귀문을 활용해 효율적으로 해결할 수 있다.

long result = func(a, b / 2);

모듈러 연산

모듈러 연산은 나머지에 관한 연산식으로 두가지 속성을 가지고 있다.

• (A+B)%C = (A%C + B%C)%C
• (A*B)%C = (A%C * B%C)%C

이러한 속성을 이용해 수의 범위를 줄인 뒤 연산을 할 수 있다.

출처) https://st-lab.tistory.com/237