[백준 / BAEKJOON] 1629번 곱셈 - C++

문제 원문

조건

시간 제한 : 0.5초 (추가 시간 없음)
메모리 제한 : 128 MB

문제

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

입력

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

출력

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

예제

풀이

제곱수를 구하는 문제입니다.

A를 N번 곱한수를 C로 나눈 나머지 값을 구하는 것이므로

Aⁿ % C

와 같이 표현할 수 있습니다.

단순하게 제곱수만큼 곱해주는 방식으로 풀면 시간을 초과하게 됩니다.

그래서 저는 Aⁿ * Aⁿ = A²ⁿ 이 되는 성질을 이용해서 N을 이진수로 변환하여 계산할 때 사용할 이진수를 구하여 이진수의 값이 1일 때만 값을 곱해주었습니다.

예제의 10, 11, 12 값을 입력하면

11 = 1011₂ 로 이진수값이 구해지고

결과 값은 (11⁴ % 12) * (11² % 12) * (11¹ % 12) 이렇게 계산됩니다.

결과적으로 시간복잡도는 O(logN + 1)이 됩니다.

성공 코드

#include <vector>
#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

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

	unsigned long long A, B, C;
	cin >> A >> B >> C;

	int nTemp = B;
	vector<int> vBinary;
	vector<unsigned long long> vVal;
	unsigned long long Result = 1;

	while (nTemp != 0)
	{
		vBinary.push_back(nTemp % 2);
		nTemp /= 2;
	}

	for (int i = 0; i < vBinary.size(); i++)
	{
		if (i == 0)
			vVal.push_back(A % C);
		else
			vVal.push_back((vVal[i - 1] * vVal[i - 1]) % C);

		if (vBinary[i])
		{
			Result = (Result * vVal[i]) % C;
		}
	}

	cout << Result << '\n';

	system("pause");

	return 0;
}

결과

Github - github.com/ledpear