아 logM에서 M은 밑을 의미합니다

100진법으로 해본다고 하면, a^(123456) 를 계산할 때, (a^1)^56 * (a^100)^34 * (a^10000)^12 로 계산한다는 의미인 것 같네요. 이때 여기서 a^1, a^100, a^10000을 계산하기 위해 100번 곱하는 걸 또 분할정복을 이용한 거듭제곱으로 하고, ^56과 ^34, ^12도 분할정복을 이용한 거듭제곱으로 한다면, M진법이라 했을 때 항 하나당 2log(M)번 계산하게 되겠네요, 항의 개수는 입력으로 들어온 수가 N이라 했을 떄 log_M(N)이 되고, 따라서 전체 시간복잡도는 log_M(N) * 2log(M)이 되네요. log_M(N) = log(N) / log(M)이므로, 얘도 결국 시간복잡도가 log(N)이 되겠네요.