作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 415 Titanic sets
时间Thu Feb 21 04:11:24 2013
415. Titanic sets
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