1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
일반적인 방식으로는 시간초과가 나는 문제이다.
따라서 분할정복을 통해 최대한 잉여계산을 줄인다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import sys
def divide_conquer(a, b):
if b == 1:
return a % C
else:
tmp = divide_conquer(a, b//2)
if b % 2 == 0:
return tmp * tmp % C
else:
return tmp * tmp * a % C
A, B, C = map(int, sys.stdin.readline().split())
answer = divide_conquer(A, B)
print(answer)
|
cs |
'알고리즘' 카테고리의 다른 글
| [BOJ] 2668 단지번호붙이기 - dfs, graph (0) | 2020.11.01 |
|---|---|
| [BOJ] 1786 찾기 - kmp알고리즘 (0) | 2020.10.29 |
| [BOJ] 12016 가장 긴 증가하는 부분수열 - 이분탐색 (0) | 2020.10.29 |
| [BOJ] 9251 LCS - DP, 문자열 (0) | 2020.10.29 |
| [Programmers] 지형 이동(BFS, MST) (0) | 2020.10.07 |