#P6357. 点阵

    ID: 6431 传统题 5000ms 1024MiB 尝试: 9 已通过: 3 难度: 10 上传者: 标签>CF2900省选/NOI-Sylvester–Gallai 定理补集计数边界格点 GCD 计数欧拉函数等比数列求和自然数幂和公式整除分块杜教筛线性筛快速幂费马小定理

点阵

题目描述

给定平面中 [0,n]×[0,n][0,n]\times[0,n] 范围内的所有整点,从中选出一个点集 SS,使得存在一条直线恰好经过 SS 中的两个点。

求满足条件的不同点集的个数,答案对 998244353998244353 取模。

输入格式

一行一个正整数 nn。

输出格式

一行一个整数,表示答案对 998244353998244353 取模后的结果。

样例

2
494
34
177109871

数据范围

1≤n≤10111\le n\le10^{11}。

原赛子任务 nn 上限 原赛分值
1 44 20
2 10210^2
3 5×1035\times10^3
4 10710^7
5 101110^{11}

原 PDF 题面