# 「DTOI-5」#1f1e33## 题目描述定义函数 $fn = displaystylesum_i = 1^n sum_j = 1^n sum_k = 1^n i + j + k = n operatornamelcmi gcdj k$给定 $n$对于所有 $1 leq i leq n$求出所有 $fi bmod 998244353$ 的值。## 输入格式一行一个整数 $n$。## 输出格式

题目描述

定义函数 $f(n) = \displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \sum_{k = 1}^n [i + j + k = n] \operatorname{lcm}(i, \gcd(j, k))$

给定 $n$，对于所有 $1 \leq i \leq n$，求出所有 $f(i) \bmod 998244353$ 的值。

输入格式

一行，一个整数 $n$。

输出格式

一行，$n$ 个整数，表示所有 $f(i) \bmod 998244353$ 的值。

样例

输入样例： 10 输出样例： 0 0 1 4 11 20 42 60 100 134

算法1

(分块) $O(n\sqrt{n})$

我们对于 $i+j+k=n$ 的 $i,j,k$ 枚举，可以将 $i$ 作为最大值来枚举，设 $i\leq j,k$，则 $i\leq \sqrt[3]{n}$，枚举 $i$ 的复杂度为 $O(\sqrt[3]{n})$，对于每个 $i$，考虑 $j,k$ 的取值，$j,k$ 的取值范围为 $[1,n]$，可以将 $[1,n]$ 分成 $\sqrt{n}$ 个块，对于每个块，我们可以预处理出 $\gcd(j,k)$ 的值，然后对于 $i$，枚举 $j,k$ 的复杂度为 $O(\sqrt{n})$，总复杂度为 $O(n\sqrt{n})$。

时间复杂度

参考文献

C++ 代码

算法2

(暴力枚举) $O(n^3\log n)$

我们对于 $i+j+k=n$ 的 $i,j,k$ 枚举，可以将 $i$ 作为最大值来枚举，设 $i\leq j,k$，则 $i\leq \sqrt[3]{n}$，枚举 $i$ 的复杂度为 $O(\sqrt[3]{n})$，对于每个 $i$，考虑 $j,k$ 的取值，$j,k$ 的取值范围为 $[1,n]$，直接枚举 $j,k$，复杂度为 $O(n^2\log n)$。

时间复杂度

参考文献

C++ 代