CF1436F Sum Over Subsets

给定一个多重集 $S$。对于所有满足以下条件的子集对 $A$ 和 $B$，计算： - $B \subset A$； - $|B| = |A| - 1$； - $A$ 中所有元素的最大公约数等于 $1$； 求 $\sum_{x \in A}{x} \cdot \sum_{x \in B}{x}$ 的总和，对 $998\,244\,353$ 取模。

第一行包含一个整数 $m$（$1 \le m \le 10^5$），表示多重集 $S$ 中不同元素的个数。 接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $freq_i$（$1 \le a_i \le 10^5, 1 \le freq_i \le 10^9$）。元素 $a_i$ 在多重集 $S$ 中出现了 $freq_i$ 次。所有 $a_i$ 互不相同。

输出所求的总和，对 $998\,244\,353$ 取模。

多重集是允许元素重复的集合。$|X|$ 表示集合 $X$ 的基数，即其中元素的个数。 $A \subset B$：集合 $A$ 是集合 $B$ 的子集。 在第一个样例中，$B=\{1\}, A=\{1,2\}$ 和 $B=\{2\}, A=\{1, 2\}$ 的乘积分别为 $1\cdot3 + 2\cdot3=9$。其他 $A$ 和 $B$ 的对子不满足给定的约束条件。 由 ChatGPT 4.1 翻译