#P9099. 「HNOI2021 省集 Day4」卿且去

    ID: 5179 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学贡献法补集计数数论Min_25 筛整除分块素数计数线性筛模逆元快速幂CF2600min25筛

「HNOI2021 省集 Day4」卿且去

题目背景

猪王睡醒,满朝公卿跑个干净。

猪王无聊,独自一人玩起游戏。

众所周知,Deltax 喜欢膜 CraZYali。

还想要,祝各位永远的神国赛胜利。

题目描述

像 Deltax 一样,猪王也很喜欢质数,所以他决定在 [2,n][2, n] 中选出若干个质数。

记这些质数大小不超过 nn 的倍数(包括自身)所构成的集合为 SS,猪王把 SS 中的数写在了一张白纸上。

猪王想选取纸面上尽量多的数,要求这些数两两不存在倍数关系,即对于任意选取的数 x,yx, y 有 x∤yx \not | y 和 y∤xy \not | x 成立。猪王将集合 SS 最多能选出几个数记为 f(S)f(S)。

猪王还没有决定他要选出那些质数。他想求对于所有 SS,∑f(S) ( mod 998244353)\sum f(S)\ (\bmod 998244353) 是多少。

输入格式

从标准输入读入。

一行一个正整数 nn。

输出格式

输出到标准输出。

一行一个正整数,表示 ∑f(S) ( mod 998244353)\sum f(S)\ (\bmod 998244353)。

样例

样例 1

4
4

其余原样例:样例 2 输入、输出;样例 3 输入、输出;样例 4 输入、输出。

数据范围与提示

  • 对于 20%20\% 的数据,n≤20n\le 20。
  • 对于 40%40\% 的数据,n≤3×103n\le 3\times 10^3。
  • 对于 60%60\% 的数据,n≤105n\le 10^5。
  • 对于 80%80\% 的数据,n≤5×107n\le 5\times 10^7。
  • 对于 100%100\% 的数据,2≤n≤10102\le n\le 10^{10}。