题目：Codeforces 链接 & Luogu 链接
如果只看前两个条件，那么这是一个比较显然的背包问题。
令 $f_{i,j}$ 表示前 $n$ 个数 $a_i$ 总和为 $j$ 的方案数。
那么对于每个 $a_i=l_i \sim r_i$ 均有
$$f_{i,j}=\sum_{k=l_i}^{r_i} f_{i-1,j-k}$$
当然直接上背包复杂度是 $\mathcal{O}(nm^2)$ 级别的，我们需要把每一个 $i$ 的所有 $f_{i,j}$ 记录一个前缀和。记
$$s_{i,j}=\sum_{k=0}^{j}f_{i,k}$$
且当 $j<0$ 时 $s_{i,j}=0$。
那么有可以一次性转移的方程：
$$f_{i,j}=s_{i-1,j-l_i}-s_{i-1,j-r_i-1}$$
时间复杂度降为了 $\mathcal{O}(nm)$。
之后就是最后一个条件：$\gcd(a_1,a_2,...,a_n)=1$。
这可以让人联想到许多数论题目的常见解决办法，比如莫比乌斯反演或者容斥，这里讲讲容斥做法。
设
$$F(x)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}[\gcd(a_1,a_2,...,a_n)=x]\left[\sum_{i}a_i \le m\right]$$
显然我们最后要求 $F(1)$。
观察到这个式子仍比较麻烦，但是条件转化成 $[x \mid \gcd(a_1,a_2,...,a_n)]$ 的话问题就会好做点。
于是再定义 $G(x)=\sum\limits_{d=1}^{\lfloor\frac{m}{x}\rfloor}F(dx)$，相当于
$$G(x)=\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}[x \mid \gcd(a_1,a_2,...,a_n)]\left[\sum_{i}a_i \le m\right]$$
然后 $[x \mid \gcd(a_1,a_2,...,a_n)]$ 这个条件就等价于限制了每个 $a_i$ 都是 $x$ 的倍数。
那我们在枚举 $a_i$ 的时候直接强制它是 $x$ 的倍数，就消去 $\gcd=1$ 的条件，可以直接上背包了。
之后还没完，我们要算的是 $F(1)$，但只求出了 $G(x)$。
观察一下 $G(x)$ 的定义式
$$G(x)=\sum_{d=1}^{\lfloor\frac{m}{x}\rfloor}F(dx)$$
移个项：
$$F(x)=G(x)-\sum_{d=2}^{\lfloor\frac{m}{x}\rfloor}F(dx)$$
那么我们从 $m$ 到 $1$ 倒序枚举 $x$，$G(x)$ 用背包求，且所有的 $F(x)$ 都可以求出来。
在枚举 $x$ 和 $x$ 的倍数这一步骤，时间复杂度为调和级数级别的，大约为 $\mathcal{O}(m \ln m)$。
因此均摊到每个 $x$ 的时间复杂度为 $\mathcal{O}(\ln m)$
对于每个 $G(x)$，我们可以用背包求。枚举 $x$ 的倍数也不怎么方便，所以我们可以将上下界以及 $m$ 都除掉 $x$，这样就可以使得 $a_i$ 连续，且减小背包容量，优化时间复杂度。
对于每个 $G(x)$，背包容量可以降为 $\lfloor\frac{m}{x}\rfloor$。
上文说了，$\sum\limits_{i=1}^m\frac{m}{x}=\mathcal{O}(m \ln m)$。
因此该做法总复杂度为 $\mathcal{O}(nm \ln m)$。
说一下写代码时的注意点：
- 前缀和数组的初始值为 $0$。
- 注意方式背包时下标变负数的情况。
- 做除法的时候，注意下界 $\frac{l_i}{x}$ 要上取整。
- 取模要取干净。
这道题就这么做完了。具体细节可以看代码：
#include <bits/stdc++.h>
#define N 100010
#define MOD 998244353
#define reg register
typedef long long ll;
using namespace std;
int n, m, l[N], r[N], dp[N], las[N], ss[N], ans, sss, slas[N];
inline int F(int x, int y){ // 上取整
return x / y + (x % y != 0);
}
int main(){
cin >> n >> m;
for(reg int i = 1; i <= n; i++) cin >> l[i] >> r[i];
for(reg int d = m; d >= 1; d--){
for(reg int j = 0; j <= m / d; j++)
dp[j] = 0, las[j] = 0, slas[j] = 0;
las[0] = slas[0] = 1;
for(reg int j = 1; j <= m / d; j++)
slas[j] = (slas[j - 1] + las[j]);
for(reg int j = 1; j <= n; j++){
for(reg int L = m / d; L >= F(l[j], d); L--){
if(L - r[j] / d > 0) dp[L] = (slas[L - F(l[j], d)] - slas[L - r[j] / d - 1] + MOD) % MOD;
else dp[L] = slas[L - F(l[j], d)];
}
for(reg int j = 0; j <= m / d; j++)
las[j] = dp[j], dp[j] = 0;
slas[0] = las[0];
for(reg int j = 1; j <= m / d; j++)
slas[j] = (slas[j - 1] + las[j]) % MOD;
}
for(reg int j = 0; j <= m / d; j++)
ss[d] = (ss[d] + las[j]) % MOD;
for(reg int j = d + d; j <= m; j += d)
ss[d] = (ss[d] - ss[j] + MOD) % MOD;
}
printf("%d\n", ss[1]);
return 0;
}