*[[Problem 415:http://projecteuler.net/problem=415]] 「タイタニック集合」 [#hb019bec]

格子点の集合 S について, そのうちの2点のみを通る直線が存在するとき, その S を''タイタニック集合''と呼ぼう.

例えば以下の集合はタイタニック集合である, S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)}, ここで (0, 1) と (2, 0) を通る直線は S の他の点を通ることがない.

一方, 集合 {(0, 0), (1, 1), (2, 2), (4, 4)} はタイタニック集合ではない, なぜなら集合内のいかなる2つの点を通る直線も他の2つの点を通るからである.

ある正の整数 '''N''' に対して, 0 ≤ '''x''', '''y''' ≤ '''N''' を満たすすべての点 ('''x''', '''y''') におけるタイタニック集合 S の数を '''T'''('''N''') としよう. '''T'''(1) = 11, '''T'''(2) = 494, '''T'''(4) = 33554178, '''T'''(111) mod 10&sup{8}; = 13500401, そして '''T'''(10&sup{5};) mod 10&sup{8}; = 63259062 であることが確かめられている.

'''T'''(10&sup{11};) mod 10&sup{8}; を求めよ.

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS