Problem 122 のバックアップ(No.1)

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 122 へ行く。
  • 1 (2009-03-01 (日) 11:54:59)

Problem 122 「効率的なべき乗計算」 †

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) を求めよ.