[C++ / 1629] 곱셈

문제

1629번: 곱셈

---

문제 설명

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

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

---

풀이 방식

이 문제는 pow를 직접 구현하는 문제이다.

 

처음에는 cmath 라이브러리에 있는 pow를 %로 나누어서 답을 내면 되겠다~ 했는데 자료형 이슈로 안되었고 했어도 아마 시간문제로 인해서 안되었을 것 같다. 당연히 for문을 통해서 구현 하더라도 연산 횟수가 많아서 안됬을 것이다.

 

그래서 이번 풀이에는 분할 정복의 개념이 사용되었다.

예를 들어,

짝수일 때는 $$A^{4} = (A^{2})^{2}$$

홀수일 때는 $$A^{5} = A * (A^{2})^{2}$$

이런 방법을 통해 연산을 줄였다.

원래는 아래와 같이 계산을 한다면 O(N)이지만, $$A^{4} = A*A*A*A$$

해당 방법을 통하면 O(logN)으로 줄일 수 있다.

 

큰 수를 대비해서 int로는 모자랄거 같아서 long long 자료형을 사용해 주었다.

---

솔루션

#include <iostream>

using namespace std;

long long a, b, c;

long long _pow(int b)
{
  if (b == 0)
    return 1;
  long long save = _pow(b / 2);
  save = save * save % c;

  if (b % 2)
    return a * save % c;

  return save;
}

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

  cin >> a >> b >> c;
  cout << _pow(b);
}