CF1559E Mocha and Stars

Mocha 想成为一名占星师。在浙江可以看到 $n$ 颗星星，第 $i$ 颗星星的亮度为 $a_i$。 Mocha 认为这 $n$ 颗星星组成了一个星座，她用 $(a_1, a_2, \ldots, a_n)$ 来表示它的状态。如果满足以下三个条件，则称该状态为“数学状态”： - 对所有 $i$（$1 \le i \le n$），$a_i$ 是区间 $[l_i, r_i]$ 内的整数。 - $\sum\limits_{i=1}^n a_i \le m$。 - $\gcd(a_1, a_2, \ldots, a_n) = 1$。 这里，$\gcd(a_1, a_2, \ldots, a_n)$ 表示整数 $a_1, a_2, \ldots, a_n$ 的最大公约数。 Mocha 想知道，这个星座有多少种不同的数学状态。由于答案可能很大，你需要输出答案对 $998\,244\,353$ 取模后的结果。 如果存在 $i$（$1 \le i \le n$）使得 $a_i \ne b_i$，则状态 $(a_1, a_2, \ldots, a_n)$ 和 $(b_1, b_2, \ldots, b_n)$ 被认为是不同的。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 50$，$1 \le m \le 10^5$），分别表示星星的数量和亮度之和的上限。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le m$），表示第 $i$ 颗星星亮度的取值范围。

输出一个整数，表示不同数学状态的数量，对 $998\,244\,353$ 取模。

在第一个样例中，这个星座有 $4$ 种不同的数学状态： - $a_1=1$，$a_2=1$。 - $a_1=1$，$a_2=2$。 - $a_1=2$，$a_2=1$。 - $a_1=3$，$a_2=1$。 由 ChatGPT 4.1 翻译