[백준 1629] 곱셈 python (수학)

 

자연수 A를 B번 곱한수를 만들고 이를 C로 나눈값을 출력하면 된다.

A ** B % C 하면 될 것 같지만 시간 복잡도 O(B)이기 때문에 시간 초과한다... 매우 크게..

이때 이진수를 활용하면 빠르게 풀이 할 수 있다.

아이디어 : 거듭제곱은 거듭제곱 간의 곱으로 표현 가능하다.

A^13이라는 값을 이진수로 표현하면 A^1101이 되는데 

1101  / 2 => 110 ... 1

110   / 2 => 11   ... 0

11     / 2 => 1     ... 1

1      / 2 => 0    ... 1

이렇게 2로 나누면 나머지가 원래 가지고 있던 이진수가 됨을 알 수 있다.

A^13 = A * A^4 * A^8

조건문 + N진수 변환 방법으로 해결 가능하다는 것을 알 수 있다.

def answer(a, b):
	ret = 1
	while b:
		if b % 2 == 1:
			ret *= a
		a = a * a
		b //= 2
	return ret

여기서 입출력과 c를 더해주면 된다.

def answer(a, b, mod):
	ret = 1
	while b:
		if b % 2 == 1:
			ret = ret * a % mod
		a = a * a % mod
		b //= 2
	return ret

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