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

 

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

 

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

1629번: 곱셈

---

 

 

해결전략

 

병합 정렬 (Merge Sort), 분할정복

 

 

long long mod_pow(long long base, long long exponent, long long mod)

 

base^exponent를 mod로 나눈 나머지를 반환한다.

 

• 지수가 0인 경우: base^0 = 1 다. 따라서 1을 반환한다.
• 지수가 홀수인 경우: base^(2 * k + 1) = (base^k) * (base^k) * base이므로 base를 한 번 곱하고 분할하여 나머지를 곱한다.
• 지수가 짝수인 경우: base^(2 * k) = (base^k) * (base^k)이므로 분할하여 나머지를 곱한다.

 

mod_pow 함수를 호출해 계산을 수행하려면 main 함수에서 기본값, 지수 및 나머지를 전달한다.

분할 정복 알고리즘을 사용하여 (A^B) mod C를 계산한다.

---

 

코드

 

#include <iostream>
using namespace std;

int a, b, c;

long long mod_pow(long long base, long long exponent, long long mod)
{
   //지수=0인 경우
   if (exponent == 0) return 1;

   //지수가 홀수
   else if (exponent % 2 == 1) {
      return (base * mod_pow(base, exponent - 1, mod)) % mod;
   }
   //지수가 짝수
   else {
      long long temp = mod_pow(base, exponent / 2, mod);
      return (temp * temp) % mod;
   }

}

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

   cin >> a >> b >> c;

   cout << mod_pow(a, b, c);

   return 0;
}

 

---