나머지1 [Kotlin] 백준 1629 : 곱셈 문제 링크 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해설 A^B\mod C를 구해야 한다. 그런데 A, B, C 모두 최대치가 Int.MAX_VALUE이기 때문에 정말 정직하게 거듭제곱을 하면 무조건 시간초과가 발생한다. 따라서 효율적인 방법을 찾아서 해결해야 한다. 이 문제는 지수 법칙을 이용하면 수월하게 해결할 수 있다. x^{2n}=(x^2)^n인 성질과 x{n+m}=x^n\times x^m인 성질을 이용하여 지수를 계속 반으로 나누면서 밑을 제곱하는 것이다. 예를 들어 2^{14}를 지수 법칙을 이용해서 .. 2023. 2. 2. 이전 1 다음
