设S是$\mathbb Z^2$的子集，若存在一条恰好只穿过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)$为$\{(x,y)\in\mathbb Z^2: 0\le x, y\le N\}$中泰坦尼克子集的总数。

可以验证$T(1) = 11, T(2) = 494, T(4) = 33554178$以及$T(111) \bmod 108 = 13500401, T(10^5) \bmod 10^8 = 63259062$。

求$T(10^11) \bmod 10^8$。

本题难度:

解答

本题用到所谓Sylvester–Gallai定理，即若一个点集有这样的性质：穿过其中任意两点的直线必定也过点集中的至少另一个点，那么事实上该点集中所有的点都共线。

由此定理可以看出，任意不共线的点集都是泰坦尼克集，所以只需要求出共线点集的总数。

枚举直线的斜率及其与x轴的交点即可获得所有直线，在每一条直线上统计至少有三个点的子集的数量即可，最总结果是$55859742$。

注：因用到cache装饰器作记忆化搜索，以下代码为Python 3，代码中还打印了进度信息。

from functools import *

n=10**11+1
mod=10**8

@cache
def check(n):
    if n==1:
        return (1,2,1)
    c,s,p=n*n,n*n*(n+1),n*n*(n+1)*(n+1)//4
    i,j=1,2
    while 1:
        v=check(n//j)
        c-=(j-i)*v[0]
        s-=(j*(j+1)-i*(i+1))//2*v[1]
        p-=(j*(j+1)*(2*j+1)-i*(i+1)*(2*i+1))//6*v[2]
        if j==n:
            break
        i=j
        j=n//(n//(j+1))
    return (c,s,p)

f=lambda x:pow(2,x,mod)-1-x-x*(x-1)//2

res=(pow(2,n*n,mod)-n*n-1-2*n*(pow(2,n,mod)-1-n-n*(n-1)//2))%mod
k=n-1
u=[0,0,0]
progress=n//10
tick=9
while k>=2:
    z=(n-1)//k
    v=check(z)
    c,s,p=v[0]-u[0],v[1]-u[1],v[2]-u[2]
    u=v
    res=(res-(p*k*k-s*k*n+c*n*n)*f(k+1)*2-(k>3)*p*4*(f(k)-k*(k-1)*(k-2)//6)-(k>2)*(p*(1-k*k-2*k)+s*(k*n+n)-c*n*n)*f(k)*2)%mod
    k=(n-1)//(z+1)
    if k<=progress:
        print(tick, "percent completed")
        progress//=10
        tick+=9
print(res%mod)