{"problem":{"name":"[THUPC 2023 初赛] 快速 LCM 变换","description":{"content":"小 I 今天学习了快速最小公倍数变换（Fast Least-Common-Multiple Transform, FLT），于是他想考考你。 给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\\cdots,r_n$。你需要做以下操作恰好一次： - 选择整数 $i,j$ 使得 $1 \\le i < j \\le n$。在序列末尾加入 $(r_i+r_j)$，并将 $r_i$ 和 $r_j$ ","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":"LGP9135"},"statements":[{"statement_type":"Markdown","content":"小 I 今天学习了快速最小公倍数变换（Fast Least-Common-Multiple Transform, FLT），于是他想考考你。\n\n给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\\cdots,r_n$。你需要做以下操作恰好一次：\n\n- 选择整数 $i,j$ 使得 $1 \\le i < j \\le n$。在序列末尾加入 $(r_i+r_j)$，并将 $r_i$ 和 $r_j$ 从序列中删除。\n\n可以注意到总共有 $\\frac{n(n-1)}{2}$ 种可能的操作，每种操作会得到一个长度为 $n-1$ 的序列。\n\n你需要对所有的这 $\\frac{n(n-1)}{2}$ 个序列，求出序列中所有元素的最小公倍数，并给出它们的和模 $998244353$ 的值。\n\n## Input\n\n输入的第一行包含一个正整数 $n$，表示序列的长度。接下来一行 $n$ 个正整数 $r_1,r_2,\\cdots,r_n$，描述初始序列。\n\n## Output\n\n输出一行一个整数，表示所有序列的最小公倍数的和模 $998244353$ 的值。\n\n[samples]\n\n## Note\n\n#### 样例解释 1\n\n- $i=1,j=2$ 时，得到的序列为 $\\{4,5\\}$，最小公倍数为 $20$；\n- $i=1,j=3$ 时，得到的序列为 $\\{3,6\\}$，最小公倍数为 $6$；\n- $i=2,j=3$ 时，得到的序列为 $\\{2,7\\}$，最小公倍数为 $14$。\n\n因此输出为 $20+6+14=40$。\n\n#### 子任务\n\n对于所有测试数据，$2 \\le n \\le 5 \\times 10^5, 1 \\le r_1,r_2,\\cdots,r_n \\le 10^6$。\n\n#### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9135","tags":["2023","数论","O2优化","快速傅里叶变换 FFT","THUPC"],"sample_group":[["3\n2 3 4\n","40\n"]],"created_at":"2026-03-03 11:09:25"}}