# 122 : 効率的なべき乗計算

$$n^{15}$$を求めるのに最も単純な方法では 14 回の掛け算が必要である.

> $$n × n × \dots × n = n^{15}$$

しかし、2進法を用いれば6 回の掛け算で計算できる.

> $$n × n = n^2$$\
> $$n^2 × n^2 = n^4$$\
> $$n^4 × n^4 = n^8$$\
> $$n^8 × n^4 = n^{12}$$\
> $$n^{12} × n^2 = n^{14}$$\
> $$n^{14} × n = n^{15}$$

ところがたった 5 回の掛け算のみでも計算できる.

> $$n × n = n^2$$\
> $$n^2 × n = n^3$$\
> $$n^3 × n^3 = n^6$$\
> $$n^6 × n^6 = n^{12}$$\
> $$n^{12} × n^3 = n^{15}$$

$$m(k)$$を$$n^k$$を求めるのに必要最低限な掛け算の回数と定義する. たとえば$$m(15)=5$$である.

$$1 ≤ k ≤ 200$$に対し、$$\sum m(k)$$を求めよ.
