- 追加された行はこの色です。
- 削除された行はこの色です。
*[[Problem 122:http://projecteuler.net/problem=122]] 「効率的なべき乗計算」 [#yf9288c3]
n&sup{15};を求めるのに最も単純な方法では 14 回の掛け算が必要である.
>>> n × n × ... × n = n&sup{15};
しかし2進法を用いれば, 6 回の掛け算で計算できる.
>>> n × n = n&sup{2};~
n&sup{2}; × n&sup{2}; = n&sup{4};~
n&sup{4}; × n&sup{4}; = n&sup{8};~
n&sup{8}; × n&sup{4}; = n&sup{12};~
n&sup{12}; × n&sup{2}; = n&sup{14};~
n&sup{14}; × n = n&sup{15};
ところがたった 5 回の掛け算のみでも計算できる.
>>> n × n = n&sup{2};~
n&sup{2}; × n = n&sup{3};~
n&sup{3}; × n&sup{3}; = n&sup{6};~
n&sup{6}; × n&sup{6}; = n&sup{12};~
n&sup{12}; × n&sup{3}; = n&sup{15};
m(k)を n&sup{k}; を求めるのに必要最低限な掛け算の回数と定義する.
たとえば m(15)=5 である.
1 ≤ k ≤ 200 に対し, Σ m(k) を求めよ.