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

• 문제

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

• 입력

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

• 출력

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

• 예제 입력

10 11 12

• 예제 출력

4

• 접근방식

쉬워 보이지만 수가 매우 커지면 오버 플로우 발생, 모듈러 연산으로 처리해야함

값이 너무 커지면 함수로 나눠서 풀어야함

모듈러 산술 연산은 분배 법칙이 성립함

• 코드

 

#include <iostream>
#include <algorithm>

using namespace std;

long long a, b, c;

long long modular(long long a, long long b) // 나눠서 푸는 방법
{
	if (b == 1) // 기저 사례 a^1이 되면 그냥 반환
		return a % c;

	long long ret = modular(a, b / 2); // 반으로 나눔
	ret = (ret * ret) % c; // 모듈러 연산으로 계속 나눔

	if (b % 2)
		ret = (ret * a) % c; // 홀수면 한번 더 2^5 = 2^2 * 2^2 * 2^1

	return ret;
}

int main() 
{
	cin >> a >> b >> c;

	cout << modular(a, b);

	return 0;
}

 

• 문제링크 : https://www.acmicpc.net/problem/1629

1629번: 곱셈