[THUPC 2023 初赛] 快速 LCM 变换

Luogu

IDLGP9135

Time2000ms

Memory512MB

DifficultyP6

2023数论O2优化快速傅里叶变换 FFTTHUPC

小 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$ 从序列中删除。可以注意到总共有 $\frac{n(n-1)}{2}$ 种可能的操作，每种操作会得到一个长度为 $n-1$ 的序列。你需要对所有的这 $\frac{n(n-1)}{2}$ 个序列，求出序列中所有元素的最小公倍数，并给出它们的和模 $998244353$ 的值。 ## Input 输入的第一行包含一个正整数 $n$，表示序列的长度。接下来一行 $n$ 个正整数 $r_1,r_2,\cdots,r_n$，描述初始序列。 ## Output 输出一行一个整数，表示所有序列的最小公倍数的和模 $998244353$ 的值。 [samples] ## Note #### 样例解释 1 - $i=1,j=2$ 时，得到的序列为 $\{4,5\}$，最小公倍数为 $20$； - $i=1,j=3$ 时，得到的序列为 $\{3,6\}$，最小公倍数为 $6$； - $i=2,j=3$ 时，得到的序列为 $\{2,7\}$，最小公倍数为 $14$。因此输出为 $20+6+14=40$。 #### 子任务对于所有测试数据，$2 \le n \le 5 \times 10^5, 1 \le r_1,r_2,\cdots,r_n \le 10^6$。 #### 题目来源来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。

Samples

Input #1

3
2 3 4

Output #1

API Response (JSON)

{
  "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$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments