33OJ
登录 注册

#P17637. [ICPC 2019 Yinchuan R] Function!

    ID: 20142 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>数学2019ICPC根号分治

[ICPC 2019 Yinchuan R] Function!

Problem Description

Define the function

fa(x)=ax(a>0∧a≠1)f_a(x) = a^x \quad (a > 0 \land a \neq 1)

for all x∈(−∞,+∞)x \in (-\infty, +\infty).

You are asked to calculate the value of

$$\sum_{a=2}^n \left( a \sum_{b=a}^n \lfloor f_{a}^{-1}(b) \rfloor \lceil f_{b}^{-1}(a) \rceil \right)$$

where fa−1(x)f_a^{-1}(x) is the inverse function of fa(x)f_a(x), ⌊x⌋\lfloor x \rfloor is the largest integer that is less than or equal to xx, and ⌈x⌉\lceil x \rceil is the smallest integer that is greater than or equal to xx.

Since the value could be very large, please output the value modulo 998244353998244353.

Input Format

An integer n (2≤n≤1012)n~(2 \leq n \leq 10^{12}) described above.

Output Format

An integer denotes the value you have calculated modulo 998244353998244353.

2
2
10
236