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

• バックアップ一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Problem 386 へ行く。
  • 1 (2012-05-27 (日) 16:34:37)

Problem 386 「反鎖の最大長」 †

ある整数を n とし, n の約数の集合を S(n) としよう.

S(n) の部分集合 A が一つの要素のみを含むか, あるいは A のいかなる要素もその他全ての要素によって割り切ることができないとき, それを S(n) の反鎖 (antichain) と呼ぼう.

例えば : S(30) = {1, 2, 3, 5, 6, 10, 15, 30}
{2, 5, 6} は S(30) の反鎖ではない.
{2, 3, 5} は S(30) の反鎖である.

S(n) の反鎖のうち最大の長さとなるもののその長さを N(n) で表すとしよう.

1 ≤ n ≤ 10&sup{8}; のときの ΣN(n) を求めよ.