BOJ - 1629: 곱셈

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

BOJ - 곱셈

문제 유형: 수학, 재귀, 분할 정복

문제 난이도: Silver I

시간 제한: 0.5초

메모리 제한: 128MB

 

문제

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

 

입력

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

 

출력

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

 

풀이

거듭제곱의 끝자리수 사이클을 이용하는 방법은 느리다.

대신, 분할 정복을 이용하여 문제를 풀 수 있다.

따로 dp테이블같은거에 저장할 필요는 없다.

한 번 이외에 추가적인 인출 및 조작이 필요한게 아니고, 케이스도 간단하기 때문이다.

 

b를 절반으로 나눈 값들을 구해서 곱해서 모듈러 c를 적용하면 된다.

만약 b가 홀수이면, a를 한번 더 곱한 값에 모듈러 c를 적용하면 된다.

오버플로우에 유의하여 풀어주면 된다.

 

또한, 반복을 이용한 방법도 있다.

지수를 이진수로 조작하여 반복적으로 제곱시켜서 b를 줄여나가는 방법이 있다.

여기서도 b가 홀수이면 a를 한번 더 곱해주면 된다.

 

 

코드

C++

재귀를 이용한 풀이

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll solve(ll a, ll b, ll c) {
  if (b == 0)
    return 1 % c;
  if (b == 1)
    return a % c;

  ll half = solve(a, b / 2, c);
  if (b % 2 == 0) {
    return (half * half) % c;
  } else {
    return (((half * half) % c) * a) % c;
  }
}

int main() {
  ll a, b, c;
  cin >> a >> b >> c;

  cout << solve(a, b, c) << "\n";
  return 0;
}

 

반복을 이용한 풀이

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll solve(ll a, ll b, ll c) {
  ll result = 1;
  a = a % c; 

  while (b > 0) {
    if (b % 2 == 1) 
      result = (result * a) % c;
    b = b >> 1; 
    a = (a * a) % c; 
  }

  return result;
}

int main() {
  ll a, b, c;
  cin >> a >> b >> c;

  cout << solve(a, b, c) << "\n";
  return 0;
}