#P9252. 某个套路求和题

    ID: 5372 传统题 1000ms 128MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-莫比乌斯函数莫比乌斯反演线性筛交换求和顺序整除分块素数计数Min_25 筛洲阁筛

某个套路求和题

题目描述

从前有个 alpha1022,他在看某本奇妙的书的时候想到了这样一个函数:

f(n)=∏d∣nμ(d)f(n) = \prod\limits_{d|n} \mu(d)

然后就有了这样一个问题:

∑i=1nf(i) mod 998244353\sum\limits_{i=1}^n f(i) \bmod 998244353

然后他就把这个问题扔给了你。

输入格式

第一行,一个正整数 nn。

输出格式

一行一个非负整数,表示答案。

5
998244351
987654
445190

数据范围与提示

对于 20%20\% 的数据,n≤106n \le 10^6;
对于 40%40\% 的数据,n≤107n \le 10^7;
对于 100%100\% 的数据,n≤1010n \le 10^{10}。