ps:problems:boj:1629
곱셈
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 1629 |
| 문제명 | 곱셈 |
| 레벨 | 실버 1 |
| 분류 |
거듭제곱의 빠른 계산 |
| 시간복잡도 | O(logn) |
| 인풋사이즈 | n<=2^31 |
| 사용한 언어 | Python |
| 제출기록 | 29200KB / 80ms |
| 최고기록 | 64ms |
| 해결날짜 | 2021/07/28 |
풀이
- 거듭제곱의 빠른 계산 (Exponentiation by squaring) 알고리즘으로 n제곱을 O(logn)에 계산하는 것을 요구하는 문제.
- 그러나 파이썬에는 모듈러 계산까지 처리 가능한 내장 pow함수가 있기 때문에, 굳이 구현할 필요 없이 그냥 가져다 쓰면 된다.
- 구현 코드가 필요하다면, 행렬로 확장시킨 행렬 제곱을 참고
코드
"""Solution code for "BOJ 1629. 곱셈".
- Problem link: https://www.acmicpc.net/problem/1629
- Solution link: http://www.teferi.net/ps/problems/boj/1629
Tags: [BinaryExponentiation]
"""
def main():
A, B, C = [int(x) for x in input().split()]
print(pow(A, B, C))
if __name__ == '__main__':
main()ps/problems/boj/1629.txt · 마지막으로 수정됨: 2021/07/28 16:10 저자 teferi
토론