問題一覧 > 通常問題

No.1931 Fraction 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : __turtle0123__turtle0123 / テスター : ぷらぷら
3 ProblemId : 8000 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-29 23:10:44

問題文

長さ $N$ の正整数列 $A,B$ が与えられるので、 $\displaystyle \sum_{i=1}^N \frac{A_i}{B_i}$ を既約分数 $\dfrac{c}{d}$ で表したときの $c,d$ を $998244353$ で割った余りを求めてください。

制約

  • $1 \le N \le 2 \times 10^5$
  • $1 \le A_i, B_i \le 2 \times 10^5$
  • $\gcd(A_i,B_i)=1$
  • 入力はすべて整数

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

出力

問題文中で定義される $c,d$ を空白区切りで $1$ 行に出力せよ。

サンプル

サンプル1
入力
2
1 2
2 3
出力
7 6

$\dfrac{1}{2}+\dfrac{2}{3}=\dfrac{7}{6}$ です。

サンプル2
入力
4
1 4
1 4
1 4
1 4
出力
1 1

サンプル3
入力
2
1 48
1 16
出力
1 12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。