← 返回题目列表

AtCoder · nadafes2022_day2_g

G. 区间 GCD

中文机器翻译题面 查看原题

配点 : 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