[백준] 1629번. 곱셈

leeeha·2022년 7월 20일

백준

목록 보기

50/185

문제

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

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제

풀이

이 문제는 배워갈 게 많은 문제였다. 단순하게 접근하면 무조건 틀린다! 어떻게 해결해야 하는지 차근차근 알아보자!

우선, 입력값으로 주어진 세 자연수의 범위가 약 21억으로, int형의 최댓값이기 때문에 a를 b번 곱한 결과는 long long 타입의 변수에 저장해야 한다.

그리고 아래처럼 단순하게 a를 b번 곱하는 방법은 시간복잡도가 O(n)이어서, b가 2,147,483,647인 최악의 경우 연산시간이 약 21초가 걸리므로 시간초과가 발생할 수밖에 없다. 따라서 분할정복을 이용하여 시간복잡도를 O(logn)으로 줄여줘야 한다.

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{ 
	ios::sync_with_stdio(0);
    cin.tie(0);

	ll a, b, c;
	cin >> a >> b >> c;

	// a를 b번 곱한다. 
	ll temp = a; 
	for(int i = 0; i < b - 1; i++){
		a *= temp; 
	}

	// 그 수를 c로 나눈 나머지 출력 
	cout << a % c << endl;

	return 0;
}

이 문제를 풀기 위해 알아야 하는 선행 지식이 있다.

지수법칙

b가 짝수: a^b = a^(b/2+b/2) = a^(b/2) * a^(b/2)

b가 홀수: a^b = a^(b/2 + b/2+1) = a^(b/2) * a^(b/2+1)

나머지 연산의 성질

(a * b) % c = (a%c * b%c) % c

→ 이 식이 왜 성립하는지는 백준의 다른 문제를 통해 알 수 있다.

위의 두 성질을 이용해서 a를 (b/2)번 곱할 때마다 c로 나눈 나머지를 구하는 방식으로 시간복잡도를 줄일 수 있다. (그리고 b가 짝수인지 홀수인지에 따라 다르게 연산)

#include <iostream>
using namespace std;
typedef long long ll;

ll a, b, c, k; 

ll power(ll b){
	if(b == 0) return 1;
	if(b == 1) return a % c;

	k = power(b / 2) % c;
	if(b % 2 == 0) return k * k % c; 
	else return k * k % c * a % c; 
}

int main()
{ 
	ios::sync_with_stdio(0);
    cin.tie(0);

	cin >> a >> b >> c; 
	cout << power(b); 

	return 0;
}