No.3785 Tree of Multiples
タグ : / 解いたユーザー数 7
作問者 :
Note
The time limit for this problem is $6$ seconds.
Problem Statement
Let $X=10^{10^{100}}$. It can be proved that there uniquely exists a rooted tree satisfying all of the following conditions. Let this tree be $T$.
- Each vertex has $1$ integer value between $1$ and $X$, inclusive, written on it, and the value written on the root is $1$ (the same value may be written on multiple vertices).
- For any vertex $u$, let $S$ be the set of all integers written on $1$ or more vertices contained in the rooted subtree rooted at $u$ (including $u$ itself), and let $x$ be the integer written on $u$. Then $S=\{mx|1\le m\le \lfloor \frac{X}{x}\rfloor\}$ holds. That is, in a rooted subtree rooted at a vertex with $x$ written on it, every multiple of $x$ between $1$ and $X$, inclusive, appears at least once, and no other value appears.
- Among the trees satisfying all of the above $2$ conditions, it has the minimum number of vertices.
For a pair of $2$ vertices $(u,v)$, let $\operatorname{score}(u,v)$ denote the minimum of the integers written on all vertices (including $u,v$ themselves) contained in the unique simple path in $T$ connecting $u$ and $v$.
There are integers $A,B$. Here, $A,B$ are given in prime factorized form, where $A=\prod\limits_{i=1}^N p_i^{\alpha _i},B=\prod\limits_{j=1}^M q_j^{\beta _j}$ ($p_i,q_j$ are prime numbers). Let $U$ be the set of all vertices of $T$ with the integer $A$ written on them, and let $V$ be the set of all vertices of $T$ with the integer $B$ written on them. Find $\sum\limits_{u\in U}\sum\limits_{v\in V} \operatorname{score}(u,v)$ modulo $998244353$.
Constraints
- $1 \le N,M \le 10^5$
- $1 \le p_i,q_j\le 10^9 (1\le i\le N, 1\le j\le M)$
- $p_i,q_j$ are prime numbers $(1\le i\le N, 1\le j\le M)$
- $p_{i_1}\ne p_{i_2} (1\le i_1 < i_2\le N)$
- $q_{j_1}\ne q_{j_2} (1\le j_1 < j_2\le M)$
- $1 \le \alpha_i,\beta_j (1\le i\le N, 1\le j\le M)$
- $\sum\limits_{i=1}^N \alpha_i, \sum\limits_{j=1}^M \beta_j \le 10^5$
- All input values are integers.
Input
The input is given in the following format.
$N\ M$ $p_1\ \alpha_1$ $\vdots$ $p_N\ \alpha_N$ $q_1\ \beta_1$ $\vdots$ $q_M\ \beta_M$
Output
Output the answer on $1$ line. End the output with a newline.
Sample
Sample 1
Input
2 1 2 1 3 1 2 3
Output
3
Here, $A=2^1\cdot 3^1=6,B=2^3=8$. The part of $T$ containing the vertices with values at most $8$ written on them is extracted as shown in the figure. As in the figure, name the vertices with $6$ written on them $u_1,u_2$, and the vertex with $8$ written on it $v_1$. Then $\operatorname{score}(u_1,v_1)=2,\operatorname{score}(u_2,v_1)=1$, so the answer is $3$.
Sample 2
Input
2 2 2 3 3 1 3 2 2 2
Output
77
Sample 3
Input
3 4 611951 20000 350377 30000 882377 40000 104729 10000 287117 60000 415087 10000 746773 10000
Output
923860980
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。