소프티어 수퍼바이러스 (python)

Problem

Solution

import sys

K, P, N = map(int, sys.stdin.readline().split())

def f(x, y):
  if y == 1:
    return x

  elif y % 2 == 0:
    answ = f(x, y / 2)
    return (answ * answ) % 1000000007
  
  else:
    answ = f(x, (y - 1) / 2)
    return (answ * answ * x) % 1000000007

answer = f(P, 10 * N) * K % 1000000007
print(answer)

입력 값이 매우 크다. 그냥 for문을 돌리면 10^16만큼 돌면서 바로 시간 초과가 된다.

모듈러 연산을 지수에 응용하여 풀이해야 하는 문제이다.

→ (a * b) % c = (a % c) * (a % c)

Reference

https://jie0025.tistory.com/440

Solution

import sys

K, P, N = map(int, sys.stdin.readline().split())

def f(x, y):
  if y == 1:
    return x

  elif y % 2 == 0:
    answ = f(x, y / 2)
    return (answ * answ) % 1000000007
  
  else:
    answ = f(x, (y - 1) / 2)
    return (answ * answ * x) % 1000000007

answer = f(P, 10 * N) * K % 1000000007
print(answer)

입력 값이 매우 크다. 그냥 for문을 돌리면 10^16만큼 돌면서 바로 시간 초과가 된다.

모듈러 연산을 지수에 응용하여 풀이해야 하는 문제이다.

→ (a * b) % c = (a % c) * (a % c)

Reference

https://jie0025.tistory.com/440