백준 1629번 곱셈 풀이

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

분할 정복을 이용한 거듭제곱, 수학

제출 일자

2025년 2월 18일 15:03:20

문제 설명

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

입력

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

출력

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

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long A, B, C, result = 0;
long long go(long long n, long long m)
{
	if (m == 1) return n % C;
	long long value = go(n, m / 2);

	value = (value * value) % C;
	if (m % 2)
		value = (value * n) % C;

	return value;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> A >> B >> C;
	cout<<go(A, B);

	return 0;
}

 

입력 값이 20억이 넘어가고 곱셈도 하기 때문에 long long 타입을 썼으며 재귀함수를 사용했다.

이때 중요한 점은 2^4 = 2^2 * 2^2 라는 점과 마지막에 나누기 연산을 하면 그전에 너무 값이 커져버리니 계속해서 %연산을 해줘야한다는점이다.