boj 1629 곱셈(실버1)

문제

boj 1629 곱셈

풀이

그냥 for문으로 제곱할 생각으로 하면
인풋값 범위가 20억이기때문에 당연히 시간복잡도 통과를 못한다.

pow 함수의 log(n) 으로 제곱연산 처리가 가능한 내부 구조를 공부해볼수 있는 문제였다.

import sys
input = sys.stdin.readline

a,b,c = map(int,input().split())

def pow2(k,n,c):
  ret = 1
  count = 0

  while(n > 0 ):
    count += 1
    if n % 2 != 0 :
      ret *= k
      ret %= c

    k *= k
    k %= c
    n //= 2

  return ret

print(pow2(a,b,c))

log(n)으로 처리 가능한 pow함수를 만들고 나중에 한번에 나누기를 해주려고 했는데
숫자가 커서 그런지 그렇게하면 시간초과가 난다.
따라서 pow함수 내에서 연산하는 과정마다 계속 c값으로 나누기 처리를 해서 숫자 크기 자체를 줄여줘야한다.

재밌는 문제였다

결과

끝