[백준 1629번] 파이썬 - 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

 

 

# 조건

• 자연수 A를 B번 곱한 수를 알고 싶은데, 구하려는 수가 매우 커질 수 있으므로 C로 나눈 나머지를 구하여라
• A, B, C는 2,147,483,647 이하의 자연수이다.

 

# 접근 방법

• 일반적인 곱셈을 활용한다면 시간초과가 날 것이다.
• 분할 정복을 이용하여 지수를 짝수와 홀수 일 때를 나눠준다.
• 짝수인 경우 - 지수가 10이라면
  • A^10 = A^5 * A^5
• 홀수인 경우
  • A^5 = A^2 * A^2 * A
• b가 홀수 = 2^9 == 2^4 2^4 2
• 즉 B가 8이라면,
  • 2^8%C == 2^4%C * 2^4%C
  • 2^4%C = 2^2%C * 2^2%C
  • 2^2%C = 2%C * 2%C
• 각 항에 대해 C로 나눈 나머지를 미리미리 구해주는 것
• 위의 연산이 가능한 이유는 분배 법칙 이용-> (AB)%C = (A%C) (B%C)
  • (10^11) % C
  • = ((10^5)% C) ((10^5)% C) (10%C)

 

# code

import sys

sys.stdin = open('input.txt')

# 분할 정복 이용

# A를 B번 곱한 수를 C로 나눈 나머지를 구하여라

# b가 짝수 = 2**8 == 2**4 * 2**4 로 나누어서 구해준다.



def multi(a, b, c):

    if b == 1:
        return a%c

	# 미리 a^(b//2)를 구해준다.
    temp = multi(a, b//2, c)

    if b % 2 == 0:

        return temp * temp % c

    else:

        return temp * temp * a % c

A, B, C = map(int, input().split())
print(multi(A, B, C))

 

 

# code 2 - 내장 함수 이용

• 파이썬에는 제곱을 지원하는 내장 함수 pow()와 math 라이브러리에 정의된 math.pow() 함수가 존재
• math.sqrt()는 x의 제곱근을 반환
• math 모듈 내의 함수들은 float형태로 반환
• 내장 함수 pow(a, b, c)는 a를 b 제곱한 값을 c로 나눈 나머지를 반환해주는 내장 함수이다. 이를 활용해서 바로 풀 수 있다.

A, B, C = map(int, input().split())
print(pow(A, B, C))