[백준][C] 1629번: 곱셈

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

 

A^B 를 % C한 값을 구하면 된다.

 

하지만 주어진 수가 최대 21억에 시간 제한은 0.5초로 O(N) 시간복잡도도 불가능한 문제이다.

 

즉, 그냥 for (int i = 0; i < B; i++)를 하면 무조건 시간 초과가 발생한다.

 

반복문을 21억번 돌려야 하기 때문이다.

 

 

최대한 연산량을 줄이는 방법을 생각해야 한다.

 

사용했던 수를 재사용 하면 연산량을 줄일 수 있다.

 

그러나 수의 최대가 21억이기에 만약 DP로 풀기 위해 배열을 만든다면 21억개의 칸을 만들어야 하므로 불가능하다.

 

그러니 거듭제곱을 분해해보자

 

예제의 10의 11제곱을 손으로 풀어보자

손으로 10을 11번 곱해도 되겠지만 거듭제곱의 성질을 사용해보자

실제로 계산해보면 맞다

 

또한 밑의 식은

으로 변경할 수 있다.

 

즉, 10^11을 10^5와 10^1 로 표현할 수 있다.

이걸 재귀함수로 반복해준다면

 

기존의 10번 반복하던 반복문을 11 -> 5 -> 2 -> 1 로 4번의 반복으로 축소할 수 있게 된다.

대략 O(logN)으로 감소시킨 것이다.

 

이것으로 시간 문제는 해결되었다

 

하지만 여전히 수가 엄청나게 크다는 문제가 있다.

21억 * 21억은 매우 큰 수 이기 때문에 몇번 만 곱해도 long long 범위는 금방 넘어갈 것이다.

 

그래서 C로 나눈 나머지를 사용하라는 것이다.

 

나머지 연산은 약간 다른 분배법칙을 적용할 수 있다.

이렇게 나머지 연산을 적용할 때 내부에 곱해지는 요소들에 나머지 연산을 다 해서 곱한 뒤에 나머지 연산을 넣어줘도 값은 같다.

 

이 방법을 사용해서 거듭제곱을 구할 때마다 C로 나머지 연산을 넣어주면 오버플로우를 방지할 수 있을 것이다.

 

C로 구현한 코드 보기

 

#include <stdio.h> 
#pragma warning(disable:4996)

long long multipow(long long a, long long b, long long c)
{
	if (b <= 1)
		return a % c;

	long long t = multipow(a, b / 2, c);
	long long tt = t * t % c;
	if (b % 2 == 0)
	{
		
		return tt % c;
	}
	else
	{
		return tt * a % c;
	}
}

int main()
{
	long long a, b, c;

	scanf("%lld %lld %lld", &a, &b, &c);

	long long ans = multipow(a, b, c);
	printf("%lld\n", ans);

	return 0;
}