← 返回题目列表

Codeforces · 1436/F

F. 子集总和

中文机器翻译题面 查看原题

给你一个多重集 $$$S$$$。在所有子集对 $$$A$$$ 和 $$$B$$$ 上,使得:

- $$$B \子集 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$$$ 为模。

示例

输入 #1

2
1 1
2 1

输出 #1

9

输入 #2

4
1 1
2 1
3 1
6 1

输出 #2

1207

输入 #3

1
1 5

输出 #3

560

注意

多重集是允许元素重合的集合。 $$$|X|$$$ 是集合 $$$X$$$ 的基数,即其中元素的数量。

$$$A \子集 B$$$:集合 $$$A$$$ 是集合 $$$B$$$ 的子集。

在第一个示例中,$$$B=\{1\}、A=\{1,2\}$$$ 和 $$$B=\{2\}、A=\{1, 2\}$$$ 的乘积等于 $$$1\cdot3 + 2\cdot3=9$$$。其他对 $$$A$$$ 和 $$$B$$$ 不满足给定的约束。