#P4376. Titanic sets

    ID: 3579 传统题 1000ms 512MiB 尝试: 3 已通过: 2 难度: 10 上传者: 标签>难度分类省选/NOI-组合数学补集计数计算几何边界格点 GCD 计数数论莫比乌斯反演狄利克雷卷积整除分块杜教筛线性筛倍数枚举快速幂扩大模数后精确整除Sylvester–Gallai 定理CF3000

Titanic sets

Titanic Sets

题目描述

若平面上的一个有限整点集合 SS 存在一条直线恰好经过其中两个点,就称 SS 为 Titanic 集合。直线可以穿过其他未被选入 SS 的整点。

例如,集合 {(0,0),(0,1),(0,2),(1,1),(2,0),(1,0)}\{(0,0),(0,1),(0,2),(1,1),(2,0),(1,0)\} 是 Titanic 集合:经过 (0,1)(0,1) 和 (2,0)(2,0) 的直线不经过该集合中的其他点。相反,集合 {(0,0),(1,1),(2,2),(4,4)}\{(0,0),(1,1),(2,2),(4,4)\} 不是 Titanic 集合:这四个点共线,任意过其中两点的直线也经过另外两点。

给定正整数 NN,设 T(N)T(N) 为从全部满足 0≤x,y≤N0\le x,y\le N 的整点中选出一个 Titanic 集合的方案数。求 T(N)T(N) 对 10810^8 取模后的结果。

输入格式

输入一行一个正整数 NN。

输出格式

输出一行一个整数,表示 T(N) mod 108T(N)\bmod 10^8。

样例

样例输入 #1

3

样例输出 #1

65465

数据范围

1≤N≤10111\le N\le 10^{11}。例如,T(1)=11T(1)=11,T(2)=494T(2)=494,T(4)=33554178T(4)=33554178;T(111) mod 108=13500401T(111)\bmod10^8=13500401,T(105) mod 108=63259062T(10^5)\bmod10^8=63259062。