power 함수 구현 (분할 정복 이용)

// Devide and Conquer algorithm 을 통한 power 함수의 구현.

---

   What is power function?   

power 함수의 정의

---

   Code   

typedef unsigned long long ull;
 
ull power(int num, int jisu) {
    if (!jisu) return 1; // num^0 = 1 이므로
    if (jisu % 2)
        return (power(num, jisu - 1) * num) % p;
 
    ull half = power(num, jisu / 2) % p;
    return (half * half) % p;
}

---

   Additional explanation   

  사실, <cmath> 혹은 <math.h> 헤더파일에 있는 pow(a, n) 을 이용하면 되긴 하다. 하지만 이 헤더파일 안에 있는 pow함수는 인자와 반환형이 double로, 바꿀 수 없다. 즉 만약 내가 10830번: 행렬 제곱 (acmicpc.net) 과 같은 문제를 풀어야 할 때는 내가 새로이 power함수를 구현해야 한다는 뜻이다. 뭐 이름을 power로 하던 myPow로 하던 당연히 그건 짜는 사람의 마음!! 난 power가 편해서 power로 하였다. 행렬의 power함수를 구현하기 위해선 우선 행렬은 matrix 이므로 인자와 반환형이 vector<vector<data_type>> 인 power함수를 만들어야 할 것이다. 이와 관련된 문제에 대한 글은 아래에 있다.

  link 제작중...