BOJ 10830 행렬 제곱

 

문제 링크 : https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

중고교 시절에 배운 지수에 관한 두 가지 규칙

 

1. 

$$ a^{x+y}=a^x a^y  $$

$$ a^{x+1} = a^x a^1 = a \cdot a^x $$

 

2.

$$ a^{xy}=(a^x)^y $$

$$ a^{2y}=(a^2)^y $$

 

 

이제 음이 아닌 정수 n 에 대해  $a^n$ 을 구함에 있어서 위의 내용들을 적용해보자.  

$$ a=3, n=5=101_{(2)} $$

인 경우에 대해서 설명하면 충분할 듯 싶다.

$$ 3^{101_{(2)}} = 3^{100_{(2)} + 1_{(2)} }= 3^{100_{(2)}} \cdot 3^1 = (3^2)^{10_{(2)} }\cdot 3 $$

지수가 1 bit 줄어들어 $3^2$ 의 $ 10_{(2)} $ 거듭제곱을 구하는 문제가 된다.

 

관찰에 의해,

지수 n 의 마지막 비트가 1 이면  $a$ 를 한 번 나중에 곱하고 $a^2$의 n/2 거듭제곱을 구하는 문제로 바뀐다.

지수 n 의 마지막 비트가 0 이면 그냥  $a^2$의 n/2 거듭제곱을 구하면 된다.

 

비트 수가 하나씩 줄어드니까 $ O(\log n ) $ 으로 동작한다.

대강 코드로 작성하면 다음과 같을 것이다. (변수의 크기 문제나 a==0 인 경우 등의 부차적인 문제는 눈감기로 한다.)

 

int recur(int a,int n){
  if(n==0) return 1;
  if(n%2) return a*recur(a*a, n/2);
  return recur(a*a, n/2);
}

 

반복문을 이용하는 버젼으로 바꾸면 다음과 같다.

 

int pow(int a,int n){
  int ans=1;
  while(n>0){
    if(n%2) ans*=a;
    a*=a;
    n/=2;
  }
  return ans;
}

 

ans=1 로 초기화했기 때문에 base case 에 대한 처리는 한 셈이다.

본디 지수법칙이란 게 곱셈의 결합 법칙에서 파생된 것이라 행렬의 곱셈에 대해서도 같은 규칙이 적용된다.

 

 

행렬의 곱셈을 정의하고 실수 곱의 항등원 1 대신 ans 를 n 차 항등행렬로 바꾸면 문제의 구조는 같다.