题目背景
标分数
题目描述
定义函数 f(x):
有一个 x0 的分数。你可以进行以下两种操作直到这个分数为 1:
- 分子 +1,然后如果这个分数可以约分,约分到最简形式。
- 分子分母同时 +1,然后如果这个分数可以约分,约分到最简形式。
f(x) 的值为最小操作次数。
给定 n,求 i=1∑nf(i)mod998244353。
输入格式
一行一个正整数 n。
输出格式
一行一个自然数,表示答案。
4
9
114
785
114514
1930181
提示
【样例解释】
f(1)=1,f(2)=2,f(3)=3,f(4)=3(41→21→1)。
【数据范围】
对于全部数据,1≤n≤1018。
本题采用捆绑测试。
Subtask 编号 |
特殊性质 |
分值 |
0 |
n=5 |
5 |
1 |
n≤10 |
20 |
2 |
n≤103 |
40 |
3 |
n≤106 |
25 |
4 |
无特殊性质 |
10 |