사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
G X P Z B
 
ps/problems/boj/1629.txt · 마지막으로 수정됨: 2021/07/28 16:10 저자 teferi