{"problem":{"name":"「DTOI-5」#1f1e33","description":{"content":"定义函数 $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$ 的值。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9308"},"statements":[{"statement_type":"Markdown","content":"定义函数 $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\n给定 $n$，对于所有 $1 \\leq i \\leq n$，**求出所有** $f(i) \\bmod 998244353$ 的值。\n\n## Input\n\n一行，一个整数 $n$。\n\n## Output\n\n一行，$n$ 个整数，表示所有 $f(i) \\bmod 998244353$ 的值。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/9pyd7oxa.png)\n\nIn the middle of night.\n\n## Note\n\n**【数据范围】**\n\n$$\n\\def\\or{\\operatorname{or}}\n%\\def\\arrayscretch{1.5}\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|}\\hline\n\\textbf{测试点编号}&n= &\\textbf{Points}\\cr\\hline\n\\sf1&100&10 \\operatorname{pts}\\cr\\hline\n\\sf2&10^3&10 \\operatorname{pts}\\cr\\hline\n\\sf3&10^4&20 \\operatorname{pts}\\cr\\hline\n\\sf4&10^5&20 \\operatorname{pts}\\cr\\hline\n\\sf5&/&40 \\operatorname{pts}\\cr\\hline\n\\end{array}\n$$\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9308","tags":["O2优化"],"sample_group":[["10","0 0 1 4 11 20 42 60 100 134"]],"created_at":"2026-03-03 11:09:25"}}