백준 1629. 곱셈

tose33 2022. 10. 10. 16:22

1629번: 곱셈

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

www.acmicpc.net

A,B,C가 모두 최대 약 20억까지 주어질수 있기 때문에 당연히 일일히 곱해서는 시간초과가 날것이다.

2^11을 생각해보자.

2를 11번 곱한값은 (2를 5번 곱한값) 곱하기 (2를 5번 곱한값) 곱하기 2 이다.

2^11 = 2^5 * 2^5 * 2

b=11을 반씩 나눠가면서 계산한다.

2^11 = 2^5 * 2^5 * 2

2^5 = 2^2 * 2^2 * 2

2^2 = 2^1 * 2^1

2^1 = 2