1286 : 另一个计数问题

时间限制Time Limit
3 秒Sec
内存限制Memory Limit
512 兆MB
提交次数Submitted
46 次Times
通过次数Solved
21 次Times

题目描述Description

给定一个 \(n - 1\) 个点的无向图,点的编号为 \(2 \sim n\)。对于所有的 \(2 \le u < v \le n\),边 \((u, v)\) 存在当且仅当 \(v\) 是 \(u\) 的正整数倍。定义 \(f(u, v)\) 表示 \(u\) 与 \(v\) 是否连通:当 \(u, v\) 连通时 \(f(u, v) = 1\),否则 \(f(u, v) = 0\)。求:

\[\left(\sum_{u = 2} ^ {n - 1} \sum_{v = u + 1} ^ n f(u, v) \cdot u \cdot v\right) \bmod {998244353}\]

输入格式Input

输入一行一个正整数 \(n\)。保证 \(4 \le n \le 10 ^ {11}\)。

输出格式Output

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

样例Sample

提示Hint

#0

\(f(u, v) = 1\) 当且仅当 \(u = 2, v = 4\),故答案为 \(2 \times 4 = 8\)。

#1

所有满足 \(f(u, v) = 1\) 的 \((u, v)\) 为:\((2, 3), (2, 4), (2, 6), (3, 4), (3, 6), (4, 6)\)。

出题Author

THU