問題一覧 > 通常問題

No.3785 Tree of Multiples

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : askr58 / テスター : 👑 AngrySadEight / テストしたAI : claude-opus-5-5
お気に入りにしたユーザー ProblemId : 13950 / 自分の提出
問題文最終更新日: 2026-10-30 20:22:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 520 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。