[AC] 1629 곱셈

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1629.cpp

이 문제는 가볍게 보면 정수 a, b, c 3개를 입력 받는다. 그리고 pow(a, b)%c를 하면 끝이다. 하지만 이렇게 쉬운문제는 풀지도 않는다. 이 문제의 요건을 보면 a, b, c전부 INT_MAX의 인풋을 받는다.

즉 최악의 경우 pow(INT_MAX, INT_MAX)의 경우가 발생한다. 당연히 이런 문제는 머리를 쓰라는 것이다.

전에 공부하면서 math.h에 담겨있는 pow함수는 단순 반복문으로 만든 함수가 아니라는걸 알았다.(확연한 속도차이)

그래서 과연 stl의 pow는 어떻게 구현이 되있나 생각해봤다. 맞는지 아닌지는 모르겠으나 내가 생각한 방법도 상당한 속도를 가진다. 

예제를 살펴보면 10 11 12 가 인풋으로 들어오고 이는 pow(10, 11)%12이다.

그런데 10^2는 100이고 100^2 는 10000인데 이는 10^4이다. 그리고 10000에 다시 제곱을 하면 결국 10^8이 된다. 

이렇게 3번만에 10^8까지 구하였다. 10씩 8번 곱하는 경우보다 훨씬 계산이 줄었다.

그리고 현재 2의 제곱씩 경우의 수를 늘려가고 있기 2^3인 8을 현재 b에서 뺀다.

남은 3은 다시 위과정을 반복한다. 

이렇게하면 매우 적은 연산으로 값을 추출할수있다.

그리고 이문제에서 주목해야할 점은 long long이어도 20억이상의 수를 곱하다보면 값이 넘어서버릴가능성이 있다. 

여기서 (a+b) mod c = (a mod c + b mod c) mod c 식을 응용하여 계속 값을 줄여준다.

그러면 답이 나온다. 이 설명이 이해가 되지 않는다면 인풋을 2 6 100 이런식으로 해서 계산해보면 이해가 될것이다.