[BOJ] 백준 1629번 곱셈

링크

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

문제

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

입력

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

출력

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

풀이

 #include <iostream>

using namespace std;

using ll = long long; 
ll func(ll a, ll b, ll c) {
	ll ans; 
	if (b == 1) return a % c; 
	ans = func(a, b/2, c); //int는 10자리가 넘는 값을 표현할 수 없다. 양수 최대값  2,147,483,647 
	ans = ans * ans % c; // long long은 20자리가 넘는 값을 표현할 수 없다. -> ans * ans * a % c는 오버 플로우가 발생한다.
	if (b%2 == 0) // 짝수라면
		return ans;
	return ans * a % c; //홀수라면
}

int main() {
	ios::sync_with_stdio(0);  
	cin.tie(0);
	ll a, b, c; 
	cin >> a >> b >> c;
	cout << func(a, b, c);
}

설명

재귀
📌 int는 10자리가 넘는 값을 표현할 수 없다.
int 양수 최대값: 2,147,483,647
📌 long long은 20자리가 넘는 값을 표현할 수 없다.
-> 따라서 ans = ans ans a % c라고 작성하면 오버 플로우가 발생한다.