BOJ 1629 곱셈
문제링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 요약 (A^B)%C를 구하는 문제 풀이 주어지는 세 수의 최댓값이 2,147,483,647이다. 지수값이 저렇게 큰수면 곱하다가 시간초과 나버린다. 시간복잡도를 줄이기 위해서 분할정복으로 해결하여야 한다. 지수 B가 짝수인 경우에는 A^B=(A^(B/2))^2 이고 홀수인 경우엔 A^B = A*(A^((B-1)/2))^2이다. 이렇게 연산을 logB개로 줄일수 있게 되고 시간복잡도도 즉 O(logB)가 된다. 숫자가 매우 크기 때문에 long lon..
2022. 3. 12.
