04.01. 곱셈[Divide and conquer][백준 1629]

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

1629번: 곱셈

 

Algorithm classification : Divide and conquer, Math

 

04.01.1. Problem

I want to know the number of times a natural number A multiplied by B times. However, since the number to be found can be very large, write a program to find the remainder after dividing it by C.

 

04.01.2. Input limit

In the first line, A, B, and C are given in order with a blank space in between. A, B, and C are all natural numbers less than or equal to 2,147,483,647.

 

04.01.3. Output

In the first line, multiply A by B times and output the remainder after dividing by C.

 

04.01.4. Solution

 제곱을 구하는 문제에서 지수가 매우 큰 경우가 존재하는 문제입니다. A^B를 A^(B/2) or A^(B/2)*A로 표현함으로써 연산횟수를 줄일 수 있습니다. 시간복잡도는 O(logB)가 되겠죠. 계산과정 자체에서 범위를 넘어설 수 있으니 int자료형말고 다른 자료형을 사용하는 것이 좋고 나머지 연산의 특성을 이용하시는 것이 좋습니다.

long long cal(long long a, long long b){
	if(b == 0) {
		return 1;	
	}
	if(b == 1){
		return a;
	}  
	if(b%2){
		return (cal(a, b-1) * a) % c;	
	}
	temp = cal(a, b/2);
	return (temp * temp) % c;
}

만약 아래와 같은 code로 실행한다면 b%2일때도 cal을 계산해서 시간을 소모할 것입니다.

	temp = cal(a, b/2);
	return b % 2 == 0 ? (temp * temp) % c : (cal(a, b-1) * a) % c;

그리고 최종적으로 출력할 때 나머지 연산을 해주면 좋겠죠.

	printf("%d", cal(a, b) % c);

여러분께 도움이 될만한 test case를 남깁니다.
2 5 100
>> 32

2147483646 2147483646 2147483647
>> 1

2147483645 3 2147483647
>> 2147483639

2147483645 4 2147483647
>> 16

2 222 41 (참고로 resursion function을 call할 때 argument를 a%c, b%c, c로 주면 틀리는 case입니다.)
>> 4

3 200 241
>>: 225

1 2 3
>> 1