G - Interval GCD Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

長さ N の正整数列 A = (A_1, \dots, A_N), B = (B_1, \dots, B_N) が与えられます。

k = 1, \dots, M について、以下の条件を全て満たす正整数列 C = (C_1, \dots, C_N) の総数を 998244353 で割った余りを求めてください。

  • A_i \leq C_i \leq B_i \, (1 \leq i \leq N)
  • \mathrm{gcd} (C_1, \dots, C_N) = k

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq A_i \leq B_i \leq 10^5 \, (1 \leq i \leq N)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
\vdots
A_N B_N

出力

M 行出力せよ。i \, (1 \leq i \leq M) 行目には、k = i のときに問題文中の条件を満たす C の総数を 998244353 で割った余りを出力せよ。

入力例 1

3 10
1 9
4 8
7 10

出力例 1

151
20
3
3
1
0
1
1
0
0

k = 4 のとき、C = (4, 4, 8), (8, 4, 8), (4, 8, 8) が条件を満たします。

入力例 2

1 1
2 100000

出力例 2

0