Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

개발하는 곰돌이

나머지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 다음

최근글 인기글

태그

구현 Map BOJ HashMap 잡담 WebClient 수학 부분합 큐 java Programming Language 문자열 그리디 spring boot 우선순위 큐 jpa 클래스 덱 비트마스킹 IntelliJ 투 포인터 정렬 배열 Kotlin Algorithm swagger Spring 스택 Spring Security 에라토스테네스의 체

전체 방문자

Today :

Yesterday :

티스토리툴바