#P1436F. Sum Over Subsets
-
ID: 5642
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Sum Over Subsets
No submission language available for this problem.
Description
You are given a multiset $S$. Over all pairs of subsets $A$ and $B$, such that:
- $B \subset A$;
- $|B| = |A| - 1$;
- greatest common divisor of all elements in $A$ is equal to one;
find the sum of $\sum_{x \in A}{x} \cdot \sum_{x \in B}{x}$, modulo $998\,244\,353$.
The first line contains one integer $m$ ($1 \le m \le 10^5$): the number of different values in the multiset $S$.
Each of the next $m$ lines contains two integers $a_i$, $freq_i$ ($1 \le a_i \le 10^5, 1 \le freq_i \le 10^9$). Element $a_i$ appears in the multiset $S$ $freq_i$ times. All $a_i$ are different.
Print the required sum, modulo $998\,244\,353$.
Input
The first line contains one integer $m$ ($1 \le m \le 10^5$): the number of different values in the multiset $S$.
Each of the next $m$ lines contains two integers $a_i$, $freq_i$ ($1 \le a_i \le 10^5, 1 \le freq_i \le 10^9$). Element $a_i$ appears in the multiset $S$ $freq_i$ times. All $a_i$ are different.
Output
Print the required sum, modulo $998\,244\,353$.
Samples
2
1 1
2 1
9
4
1 1
2 1
3 1
6 1
1207
1
1 5
560
Note
A multiset is a set where elements are allowed to coincide. $|X|$ is the cardinality of a set $X$, the number of elements in it.
$A \subset B$: Set $A$ is a subset of a set $B$.
In the first example $B=\{1\}, A=\{1,2\}$ and $B=\{2\}, A=\{1, 2\}$ have a product equal to $1\cdot3 + 2\cdot3=9$. Other pairs of $A$ and $B$ don't satisfy the given constraints.