BOJ 1629 : 곱셈

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/1629

 

 

A를 B번 곱할 때, B가 최대 2,147,483,647이므로, 2,147,483,647번 곱하면 연산 비용이 너무 많이 든다.

즉, O(B)의 비용이 든다.

 

하지만 분할 정복을 이용하면, O(logB)로 해결 가능하다.

 

만약 A를 100번 곱해야 한다고 생각해보자.

 

A¹⁰⁰ = A⁵⁰ * A⁵⁰

A⁵⁰ = A²⁵ * A²⁵

A²⁵ = A¹² * A¹³

 

A¹² = A⁶ * A⁶

A¹³ = A⁶ * A⁷

 

A⁶ = A³ * A³

A⁷ = A³ * A⁴

 

A³ = A * A²

A⁴ = A² * A²

 

A² = A * A

 

따라서, 재귀 함수를 이용해 답을 (log100)번만에 찾을 수 있다.

typedef unsigned long long int ull;

ull multiply(ull a, ull b)
{
	if (b == 0) return 1;
	else if (b == 1) return a % C;
	else if (b & 1) return (a * multiply(a, b - 1)) % C;
	else
	{
		ull tmp = multiply(a, b / 2);

		return (tmp * tmp) % C;
	}
}

A⁰은 1이므로, 1을 return하고, A¹은 A이므로 A를 return한다.

곱해야하는 수 B가 홀수라면 B = 1 + (B - 1)[짝수]이므로 A * A^{(B - 1)}을 한다.

그렇지 않다면 짝수이므로 절반으로 나누고 곱하면 된다.

 

실제 문제에서는 나머지를 한 값을 원하므로 

(A * B) mod C = (A mod C * B mod C) mod C 공식을 이용하면 된다.

즉, 매번 곱할 때 마다 나머지 연산을 해주면 된다.

---

재귀 함수말고도 이진수를 이용하면 문제를 해결할 수 있다.

 

100은 이진법으로 나타내면 (0110 0100)₂ = 2² + 2⁵ + 2⁶ = 4 + 32 + 64 = 100 이다.

 

따라서 A를 100번 곱한다는 것은, (ans = 1로 시작)

B = 100, 짝수	(0110 0100)2		A * A = A2
B = 50, 짝수	(0110 010)2		A2 * A2 = A4
B = 25, 홀수	(0110 01)2	ans = ans * A4 = 1 * A4로 저장.	A4 * A4 = A8
B = 12, 짝수	(0110 0)2		A8 * A8 = A16
B = 6, 짝수	(0110)2		A16 * A16 = A32
B = 3, 홀수	(011)2	ans = ans * A32 = A4 * A32 = A36으로 저장.	A32 * A32 = A64
B = 1, 홀수	(01)2	ans = ans * A64 = A36 * A64 = A100으로 저장.	A64 * A64 = A128
B = 0	종료

이다.

 

즉, B를 계속 나눠가면서 B가 홀수인 경우 제곱되는 A의 값을 ans에 곱해주면 된다.

두 방법 모두 아래의 코드를 참고하자.

#include <stdio.h>

typedef unsigned long long int ull;

ull A, B, C;

ull multiply(ull a, ull b)
{
	if (b == 0) return 1;
	else if (b == 1) return a % C;
	else if (b & 1) return (a * multiply(a, b - 1)) % C;
	else
	{
		ull tmp = multiply(a, b / 2);

		return (tmp * tmp) % C;
	}
}

int main(void)
{
	ull ans;
	ull mul;

	scanf("%lld %lld %lld", &A, &B, &C);

	/*
	printf("%lld\n", multiply(A, B) % C);
	return 0;
	*/

	mul = A;
	ans = 1LL;
	while (B > 0)
	{
		if (B % 2 == 1) ans = (ans % C) * (mul % C);

		mul = (mul % C) * (mul % C);
		B /= 2;
	}

	printf("%d\n", ans % C);

	return 0;
}