P9135 [THUPC 2023 Preliminary] Fast LCM Transform

Little I is learning the Fast Least-Common-Multiple Transform (Fast Least-Common-Multiple Transform, FLT), so he wants to test you. You are given a positive integer sequence $r_1, r_2, \cdots, r_n$ of length $n$. You need to perform the following operation exactly once: - Choose integers $i, j$ such that $1 \le i < j \le n$. Append $(r_i + r_j)$ to the end of the sequence, and delete $r_i$ and $r_j$ from the sequence. Note that there are $\frac{n(n-1)}{2}$ possible operations in total, and each operation produces a sequence of length $n-1$. For all these $\frac{n(n-1)}{2}$ sequences, you need to compute the least common multiple of all elements in the sequence, and output the sum of these values modulo $998244353$.

The first line contains a positive integer $n$, representing the length of the sequence. The next line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, describing the initial sequence.

Output one integer on one line, representing the sum of the least common multiples of all resulting sequences modulo $998244353$.

#### Sample Explanation 1 - When $i = 1, j = 2$, the resulting sequence is $\{4, 5\}$, and the least common multiple is $20$. - When $i = 1, j = 3$, the resulting sequence is $\{3, 6\}$, and the least common multiple is $6$. - When $i = 2, j = 3$, the resulting sequence is $\{2, 7\}$, and the least common multiple is $14$. Therefore, the output is $20 + 6 + 14 = 40$. #### Subtasks For all testdata, $2 \le n \le 5 \times 10^5$, and $1 \le r_1, r_2, \cdots, r_n \le 10^6$. #### Source From the 2023 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2023) Preliminary. Solutions and other resources are available at . Translated by ChatGPT 5