장동호
/
코딩테스트 뽀개기
/
BOJ 1629 곱셉
Search
BOJ 1629 곱셉
태그
재귀
수학
URL
https://www.acmicpc.net/problem/1629
문제 설명
•
자연수 A를 B번 곱하고 이를 C로 나눈 나머지를 구하는 문제
예제 입력/출력
•
입력1
10 11 12
Plain Text
복사
•
출력1
4
Plain Text
복사
제약 조건
•
1
≤
A
,
B
,
C
≤
2
,
147
,
483
,
647
1 ≤ A, B, C ≤ 2,147,483,647
1
≤
A
,
B
,
C
≤
2
,
147
,
483
,
647
문제 풀이
선행 지식
모듈러 합동 공식
접근1
반복문으로 곱셉하는 방식
-
O
(
B
)
O(B)
O
(
B
)
접근2
재귀적 모듈러 거듭제곱
-
O
(
l
o
g
B
)
O(log B)
O
(
l
o
g
B
)
풀이 코드
접근2
재귀적 모듈러 거듭제곱
-
O
(
l
o
g
B
)
O(log B)
O
(
l
o
g
B
)
참고 문헌
TISTORY
[실전 알고리즘] 0x0B강 - 재귀
TISTORY
[백준]1629번 곱셈 c/c++
TISTORY
백준 알고리즘 1629번: 곱셈
