Mocha and Stars
Contest: Codeforces Round 738 (Div. 2)
Difficulty rating: 2200
Tags: combinatorics, dp, fft, math, number theory

Mocha wants to be an astrologer. There are $$$n$$$ stars which can be seen in Zhijiang, and the brightness of the $$$i$$$-th star is $$$a_i$$$.

Mocha considers that these $$$n$$$ stars form a constellation, and she uses $$$(a_1,a_2,\ldots,a_n)$$$ to show its state. A state is called mathematical if all of the following three conditions are satisfied:

- For all $$$i$$$ ($$$1\le i\le n$$$), $$$a_i$$$ is an integer in the range $$$[l_i, r_i]$$$.
- $$$\sum \limits _{i=1} ^ n a_i \le m$$$.
- $$$\gcd(a_1,a_2,\ldots,a_n)=1$$$.

Here, $$$\gcd(a_1,a_2,\ldots,a_n)$$$ denotes the greatest common divisor (GCD) of integers $$$a_1,a_2,\ldots,a_n$$$.

Mocha is wondering how many different mathematical states of this constellation exist. Because the answer may be large, you must find it modulo $$$998\,244\,353$$$.

Two states $$$(a_1,a_2,\ldots,a_n)$$$ and $$$(b_1,b_2,\ldots,b_n)$$$ are considered different if there exists $$$i$$$ ($$$1\le i\le n$$$) such that $$$a_i \ne b_i$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 50$$$, $$$1 \le m \le 10^5$$$) — the number of stars and the upper bound of the sum of the brightness of stars.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le m$$$) — the range of the brightness of the $$$i$$$-th star.

Output format:
Print a single integer — the number of different mathematical states of this constellation, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, there are $$$4$$$ different mathematical states of this constellation:

- $$$a_1=1$$$, $$$a_2=1$$$.
- $$$a_1=1$$$, $$$a_2=2$$$.
- $$$a_1=2$$$, $$$a_2=1$$$.
- $$$a_1=3$$$, $$$a_2=1$$$.

Example input:
2 4
1 3
1 2

Example output:
4

Example input:
5 10
1 10
1 10
1 10
1 10
1 10

Example output:
251

Editorial:
We firstly ignore the constraint of $$$\gcd$$$, let $$$f([l_1,l_2,\ldots,l_n],[r_1,r_2,\ldots,r_n],M)$$$ be the number of integers $$$(a_1,a_2,\cdots,a_n)$$$ satisfy the following two conditions:
• For all $$$i$$$ ($$$1\le i\le n$$$), $$$a_i$$$ is an integer in the range $$$[l_i, r_i]$$$.
• $$$\sum \limits _{i=1} ^ n a_i \le m$$$.
We can compute it in $$$O(nM)$$$ by Knapsack DP optimized by prefix-sums.
Then we consider about the constraint of $$$\gcd$$$, let $$$\mu(n)$$$ be Mobius function, and $$$g(a_1,a_2,\ldots,a_n)$$$ be $$$1$$$ if $$$(a_1,a_2,\cdots,a_n)$$$ satisfies the two conditions we mentioned about (without the constraint of $$$\gcd$$$), otherwise it will be $$$0$$$.
The answer we want is: $$$$$$ \begin{aligned} &\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}[\gcd(a_1,a_2,\ldots,a_n)=1]g(a_1,a_2,\ldots,a_n) \newline =&\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}g(a_1,a_2,\ldots,a_n)\sum_{d \mid \gcd(a_1,a_2,\ldots,a_n)}\mu(d) \newline =&\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}\cdots\sum_{a_n=l_n}^{r_n}g(a_1,a_2,\ldots,a_n)\sum_{d\mid a_1,d\mid a_2,\ldots,d \mid a_n}\mu(d) \newline =&\sum_{d=1}^M\mu(d)\sum_{a_1=\lceil\frac{l_1}{d}\rceil}^{\lfloor\frac{r_1}{d}\rfloor}\sum_{a_2=\lceil\frac{l_2}{d}\rceil}^{\lfloor\frac{r_2}{d}\rfloor}\cdots\sum_{a_n=\lceil\frac{l_n}{d}\rceil}^{\lfloor\frac{r_n}{d}\rfloor}g(a_1d,a_2d,\ldots,a_nd) \newline \end{aligned} $$$$$$ Since $$$\sum \limits _{i=1} ^n a_id \le M$$$ can be changed to $$$\sum \limits _{i=1} ^n a_i \le \left\lfloor\dfrac{M}{d}\right\rfloor$$$, it equals: $$$$$$ \begin{aligned} \sum_{d=1}^M\mu(d)f\left(\left\lceil\dfrac{l_1}{d}\right\rceil,\left\lceil\dfrac{l_2}{d}\right\rceil,\ldots,\left\lceil\dfrac{l_n}{d}\right\rceil,\left\lfloor\dfrac{r_1}{d}\right\rfloor,\left\lfloor\dfrac{r_2}{d}\right\rfloor,\ldots,\left\lfloor\dfrac{r_n}{d}\right\rfloor,\left\lfloor\dfrac{M}{d}\right\rfloor\right) \end{aligned} $$$$$$ So we can compute it in $$$O\left(n\sum \limits _{i=1}^M \left\lfloor\dfrac{M}{i}\right\rfloor\right)=O(nM \log M)$$$.