곱셈

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	80202	21806	16017	26.282%

문제

자연수 A를 B번 곱한 수를 알고 싶다.

단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다.

A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

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

예제 입력 1

10 11 12

예제 출력 1

4

출처

• 문제를 만든 사람: author5

알고리즘 분류

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

---

문제의 포인트

문제에서 구하는 내용은 간단하다

A ^ B % C 의 값을 구하는 것

A, B, C는 모두 2,147,483,647 이하의 자연수이므로

– A를 2,147,483,647번(약 21억) 곱하는 연산으로 시간 초과 => 2,147,483,647^2,147,483,647

– 연산중 변수 값의 오버플로우로 인한 오류

위의 문제를 해결하기 위해서는

모듈러 산술 / 지수법칙을 사용하여 해결할 수 있다.

---

모듈러 산술 : https://sskl660.tistory.com/75

---

지수 법칙 : https://ko.khanacademy.org/math/cc-eighth-grade-math/cc-8th-numbers-operations/cc-8th-exponent-properties/a/exponent-properties-review

위의 식을 재귀로 계속 반복하여 B = 1이 될 때까지 진행

추가적으로 B가 홀수 일 때 B / B-1 로 인하여 B = 0 이 되는 경우를 따로 처리해 주어야 한다.

(필기가 가능한 태블릿을 하나 구매할까…. ㅠ)

통과된 코드

#include <iostream>

using namespace std;

int A, B, C;

// 입력을 받는 함수
void GetInput()
{
	cin >> A >> B >> C;
}

long long int Calculate(int B)
{
	if (B == 0) { return 1; } //  N ^ 0 = 1
	else if (B == 1) { return (A % C); }
	
	if (B % 2 == 0){ // 짝수일 경우
		long long int temp = Calculate(B / 2);
		return (temp * temp) % C;
	}
	else { // 홀수일 경우
		return (A * Calculate(B-1)) % C;
	}
}

int main()
{
	GetInput();
	cout << Calculate(B);
	return 0;
}

이 문제를 풀면서 내가 수학을 얼마나 못하는지 깨달았다.

젠장