luogu#P11397. 界分数

    ID: 35212 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>2024数论洛谷原创洛谷月赛Ad-hoc洛谷比赛

界分数

题目背景

标分数

题目描述

定义函数 f(x)f(x)

有一个 0x\frac{0}{x} 的分数。你可以进行以下两种操作直到这个分数为 11

  1. 分子 +1+1,然后如果这个分数可以约分,约分到最简形式。
  2. 分子分母同时 +1+1,然后如果这个分数可以约分,约分到最简形式。

f(x)f(x) 的值为最小操作次数。

给定 nn,求 i=1nf(i)mod998244353\sum\limits_{i=1}^n f(i) \bmod 998244353

输入格式

一行一个正整数 nn

输出格式

一行一个自然数,表示答案。

4
9
114
785
114514
1930181

提示

【样例解释】

f(1)=1f(1)=1f(2)=2f(2)=2f(3)=3f(3)=3f(4)=3f(4)=314121\frac{1}{4}\rightarrow\frac{1}{2}\rightarrow 1)。

【数据范围】

对于全部数据,1n10181\le n \le 10^{18}

本题采用捆绑测试。

Subtask 编号 特殊性质 分值
0 n=5n=5 55
1 n10n\le 10 2020
2 n103n\le 10^3 4040
3 n106n\le 10^6 2525
4 无特殊性质 1010