(1629) 곱셈

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

단계별로 풀어보기

24단계(분할 정복) 4번째

 

 

 

단순히 A를 B번 곱하면 O(B)가 걸린다.

B가 짝수라면 A^B = A^(B/2) * A^(B/2)이다.

B가 홀수라면 A^B = A^(B-1/2) * A^(B-1/2) * A이다.

이렇게 분할해서 풀면 O(log B)로 시간복잡도를 줄일 수 있다.

 

 

 

#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  
  cin >> a >> b >> c;
  
  auto func= [&](auto self, long x, long y) -> long {
    if(y==0)  return 1L;
    else if(y==1)  return x%c;
    
    long t= self(self, x, y/2);
    
    if(y&1){
      return (((t*t)%c)*x)%c;
    }else{
      return (t*t)%c;
    }
  };
  
  cout << func(func, a, b);
  
  return 0;
}

 

 

 

거듭제곱은 재귀 말고 반복문으로도 구현할 수 있다. 조금 더 복잡하지만 기본적인 논리는 같다.

#include <iostream>
using namespace std;

long power(long base, long expo, long mod){
  long res= 1;
  base%= mod;
  
  while(expo){
    if(expo&1)  res= (res*base)%mod;
    base= (base*base)%mod;
    expo/= 2;
  }
  
  return res;
}

int main() {
  int a, b, c;
  
  cin >> a >> b >> c;
  
  cout << power(a, b, c);
  
  return 0;
}