[Silver / 1629] 곱셈

문제 링크

---

🔷 분류

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

✒️ 문제 설명

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
using namespace std;
typedef long long ll;

ll mult(ll a, ll b, ll c){
  if(b == 0) {
    return 1;
  }

  ll half = mult(a, b/2, c);

  if(b % 2 == 0) { // 짝수면 
    return (half * half) % c;
  } else { // 홀수면
    return ((half * half) % c * a) % c;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  ll a, b, c;
  cin >> a >> b >> c;
  cout << mult(a % c, b, c);
}