Problem 8F. Lcm and Gcd

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 8F. Lcm and Gcd

时间限制:1s

空间限制:256MB

Description

给定一个整数 \(n\) ,对于所有正整数 \((a, b, c)\) 的三元组,计算 \(\sum{\operatorname{lcm}(c, \gcd(a, b))}\) ,其中 \(a + b + c = n\) 。

\(gcd(x,y)\) 表示 \(x\) 和 \(y\) 的 最大公因数 ,\(lcm(x, y)\) 表示 \(x\) 和 \(y\) 的 最小公倍数

Input Format

输入一行一个整数 \(n\) , ( \(3 \le n \le 10^5\) )。

Output Format

输出一个整数 - \(\sum{\operatorname{lcm}(c, \gcd(a, b))}\) 。由于答案可能非常大,将答案对 \(998244353\) 取模。

Input Example #1:

3

Output Example #1:

1

Input Example #2:

5

Output Example #2:

11

Input Example #3:

69228

Output Example #3:

778304278

Note

在第一个示例中,只有一个合适的三元组 \((1, 1, 1)\) 。所以答案是 \(\operatorname{lcm}(1, \gcd(1, 1)) = \operatorname{lcm}(1, 1) = 1\) 。

在第二个例子中, \(\operatorname{lcm}(1, \gcd(3, 1)) + \operatorname{lcm}(1, \gcd(2, 2)) + \operatorname{lcm}(1, \gcd(1, 3)) + \operatorname{lcm}(2, \gcd(2, 1)) + \operatorname{lcm}(2, \gcd(1, 2)) + \operatorname{lcm}(3, \gcd(1, 1)) \)

= \( \operatorname{lcm}(1, 1) + \operatorname{lcm}(1, 2) + \operatorname{lcm}(1, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(2, 1) + \operatorname{lcm}(3, 1) = 1 + 2 + 1 + 2 + 2 + 3 = 11\) 。

2023秋 悬赏令第八周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-11-26 18:30
结束于
2023-12-03 00:00
持续时间
149.5 小时
主持人
参赛人数
54