http://projecteuler.net/problem=415
如果在一個由二維坐標上的格子點組成的點集合S之中,存在一條直線恰通過這個集合中
的兩個點,則我們稱這個點集合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)}不是泰坦集合,因為任兩個點所決定的
直線也必定通過其他兩個點。
對於任意的正整數N,令T(N)表示在0 ≦ x, y ≦ N的限制下,泰坦集合的總數。
可以證明T(1) = 11,T(2) = 494,T(4) = 33554178,T(111) mod 10^8 = 13500401以及
T(10^5) mod 10^8 = 63259062。
請求出T(10^11) mod 10^8。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 129.2.129.163
415. Titanic sets