알고리즘 :: 백준 :: 1629 - 곱셈

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

입력: 2,147,483,647 이하의 자연수 A, B, C

출력: A를 B번 곱한 수를 C로 나눈 나머지  ($A^B \pmod C$)

✏️ 문제풀이

첫 시도 :: 잘못된 접근

나누는 수에 따라 나머지가 반복되는 성질이 있는 일부 수가 있는데, 모든 수가 그럴 것이라 생각하고 풀었습니다.

그러나, 반드시 모든 수가 나머지가 반복되진 않습니다.

ull A, B, C, result = 1;
cin >> A >> B >> C;

set<ull> s;

while (B--) {
	result = (result * A) % C;
	if (s.find(result) != s.end()) break;
	s.insert(result);
}
cout << *next(begin(s), B % s.size()) << '\n';

• `std::set<int>`을 이용해서, 나머지가 반복될 때 멈춥니다.
• 예제입력의 `10 11 12`의 경우, 나머지가 10 -> 4 -> 4 -> 4 -> 4... 로 4가 반복되니
• 반복을 발견하면 바로 O(1)에 나머지를 구할 수 있지 않나? 라는 생각을 했습니다.

올바른 풀이

A, B, C 모두 범위가 약 21억이고 A^B를 C로 나눈 나머지를 구해야 하므로,

• 중간 계산과정에서 `int` 범위를 넘을 수 있다는 점,
• $O(n)$으로 풀면 시간초과가 난다는 점을 파악해야 합니다.

핵심 아이디어는 분할정복입니다.

• $(A^B)\ \% \  C$는 $(A^{B/2} \times A^{B/2}))\ \% \ C$와 같으며
• $(A^{B/2})\ \% \ C$는 $(A^{B/4} \times A^{B/4})\ \% \ C$와 같으며
• … (반복) ....

이 아이디어를 적용하면, 즉, $O(log_2N)$으로 해결할 수 있습니다.

B를 나눌 때, 홀수일 경우에는 B를 한 번 더 곱해서 보상해줘야 한다는 점을 잊지 맙시다.
(e.g. 5 = 2 + 2 ( + 1 보상해줘야 함 ))

📝 코드

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

// O(n) -> O(log₂N)
ull solve(ull A, ull B, ull C) {
	if (B == 1) return A % C;
	
	ull ret = solve(A, B / 2, C);		// get A^(n/2)
	ret = (ret * ret) % C; 				// A^n = A^(n/2) * A^(n/2)
	if (B & 1) ret = (ret * A) % C;		// compensate one if B is odd.
	
	return ret;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	ull A, B, C;
	cin >> A >> B >> C;
	cout << solve(A, B, C) << '\n';
}

 

🔗 코드 링크

🕧 결과