Description

Margatroid退役之后沉迷文化课

这天，写完数学作业之后的他脑洞大开，决定出一道比NOIP2017 D1T1《小凯的疑惑math》还要好的题

题面是这样的

$$ f(n)=n^2\\ g(n)=\sum_{i=1}^{n^3}[f(i)<n]\\\\ k(n)=\sum_{i=1}^{n^3}[g(i)<n] $$

试求$k(n)\ \text{mod}\ 998244353$

Input

一行一个整数$n$

Output

一行一个整数$k(n)$

Sample Input

1

Sample Output

1

Hint

出题人沉迷文化课，无心造数据，满足数据是以10为首项，10为公比的等比数列

题解

由题： $$g(n) = \sum_{i=1} [i^2 < n]$$

显然：

$$g(n) =

\begin{cases}

\sqrt n-1& \text{ n 是完全平方数}\\

\lfloor \sqrt n \rfloor& \text{otherwise}

\end{cases}$$

构造等价函数： $$g(n) = \lfloor \sqrt {n-1} \rfloor$$

同理，由题： $$k(n) = \sum_{i=1} [\sqrt {i-1} < n]$$

因为 $n$ 是正整数，所以 $k(n)$ 等价于：

\begin{aligned}    

     k(n) &= \sum_{i=1} [i-1 < n^2]\\

     & = \sum_{i=1} [i <= n^2]\\

     & = n^2

\end{aligned}

1 //It is made by Awson on 2018.1.2 2 #include 
     
       3 #include