<백준 1629번> 곱셈

문제

---

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

 

입력

---

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

 

출력

---

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

 

예제 입력 1 

---

10 11 12

 

예제 출력 1 

---

4

 

 

 

 

접근방법

---

예를 들어 2를 10번 곱한다면 2를 10번 곱하는 것은 2를 5번 곱하는것과 2를 5번 곱하는 것의 곱이다. 계속 쪼개나간다.

즉, 쪼개서 표현할 수 있고 겹치는 부분은 메모이제이션으로 이미 계산한 것을 저장해둔다.

(분할 정복)

 

1. 반으로 쪼개는 것을 생각

2. 재귀함수 활용

3. 기저 사례 확인

4. 약 21억의 값을 가질 수 있으므로, long long 타입으로 설정 (int는 약 20억까지 표현가능)

 

코드

---

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll; // 20억 넘기 때문
ll a, b, c;

ll go(ll a, ll b){
    if(b == 1) return a % c; // 기저 사례 
    ll _c = go(a, b / 2);
    _c = (_c * _c) % c;
    if(b % 2)_c = (_c * a)% c; // 홀수라면 
    return _c;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> a >> b >> c;
    cout << go(a, b) << "\n";
    return 0;
}