DTOI-5 #1f1e33 数论：最小公倍数与最大公约数的应用

题目描述

定义函数 $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$ 的值。

样例 #1

样例输入 #1

样例输出 #1

0 0 1 4 11 20 42 60 100 134

提示

【数据范围】

$$\def\or{\operatorname{or}}%\def\arrayscretch{1.5}\def\arraystretch{1.5}\begin{array}{|c|c|c|}\hline\textbf{测试点编号}&n= &\textbf{Points}\cr\hline\sf1&100&10 \operatorname{pts}\cr\hline\sf2&10^3&10 \operatorname{pts}\cr\hline\sf3&10^4&20 \operatorname{pts}\cr\hline\sf4&10^5&20 \operatorname{pts}\cr\hline\sf5&/&40 \operatorname{pts}\cr\hline\end{array}$$对于 $100%$ 的数据，$1 \leq n \leq 10^6$。

算法分析

算法1：分块

思路

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

时间复杂度

$O(n\sqrt{n})$

算法2：暴力枚举

思路

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

时间复杂度

$O(n^3\log n)$

C++ 代码实现cpp#include #include

using namespace std;

const int MOD = 998244353;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}

int lcm(int a, int b) { return 1ll * a * b / gcd(a, b);}

int main() { int n; cin >> n;

for (int i = 1; i <= n; i++) {        int ans = 0;        for (int j = 1; j <= i; j++) {            for (int k = 1; k <= i - j; k++) {                if (j + k <= i) {                    ans = (ans + lcm(j, gcd(k, i - j - k))) % MOD;                }            }        }        cout << ans << ' ';    }

return 0;}