问题重述

给定 $n$ 个区间 $[l_i, r_i]$ 和一个上界 $m$，求满足以下条件的整数序列 $(a_1,\dots,a_n)$ 的个数（模 $998244353$）：

1. $l_i \le a_i \le r_i$；
2. $\sum_{i=1}^n a_i \le m$；
3. $\gcd(a_1,\dots,a_n)=1$。

算法思路

第一步：莫比乌斯反演

条件 $\gcd=1$ 很难直接处理，我们考虑其补集：对于任意 $d>1$，统计所有 $a_i$ 都是 $d$ 的倍数的序列。记

$$F(d) = \#\{(a_1,\dots,a_n) \mid l_i\le a_i\le r_i,\ \sum a_i\le m,\ d\mid a_i\ \forall i\}. $$

那么由容斥原理，答案即为

$$\text{Ans} = \sum_{d=1}^m \mu(d)\cdot F(d),$$

其中 $\mu$ 是莫比乌斯函数。这是因为 $\sum_{d\mid g} \mu(d) = [g=1]$，而 $\gcd(a)=g$ 时，所有 $a_i$ 都是 $g$ 的倍数，但为了只统计 $\gcd=1$，我们需对 $g$ 的因子做容斥。实际上，上式就是经典的莫比乌斯反演形式：设 $G(d)$ 为 $d$ 整除所有 $a_i$ 的方案数，则 $G(d)=\sum_{d\mid g} f(g)$，其中 $f(g)$ 是 $\gcd=g$ 的方案数，那么 $f(1)=\sum_{d} \mu(d) G(d)$。这里 $F(d)=G(d)$。

因此，我们只需对所有 $d=1\dots m$ 计算 $F(d)$，再乘以 $\mu(d)$ 求和即可。

第二步：计算 $F(d)$

固定 $d$，令 $b_i = a_i/d$，则 $b_i$ 为整数，且满足

$$\left\lceil \frac{l_i}{d} \right\rceil \le b_i \le \left\lfloor \frac{r_i}{d} \right\rfloor, $$

以及

$$\sum b_i \le \left\lfloor \frac{m}{d} \right\rfloor. $$

记 $L_i = \lceil l_i/d \rceil$，$R_i = \lfloor r_i/d \rfloor$，$M = \lfloor m/d \rfloor$。如果存在 $i$ 使得 $L_i > R_i$，则 $F(d)=0$。

现在问题转化为：求有多少个长度为 $n$ 的整数序列 $(b_1,\dots,b_n)$，满足 $L_i\le b_i\le R_i$，且 $\sum b_i \le M$。

这是一个经典的带上下界的计数问题，可以用动态规划求解。

第三步：DP 及其优化

设 $dp[t]$ 表示当前已经考虑了前 $i$ 个数，且总和为 $t$ 的方案数。初始 $dp[0]=1$，其余为 $0$。

对于第 $i+1$ 个数，其取值区间为 $[L_{i+1}, R_{i+1}]$，则新状态 $dp'$ 满足

$$dp'[t] = \sum_{b=L_{i+1}}^{R_{i+1}} dp[t-b] \quad (\text{要求 } t-b \ge 0). $$

直接转移需要枚举 $b$，复杂度为 $O(M \cdot (R_{i+1}-L_{i+1}+1))$，会超时。由于区间是连续的，我们可以用前缀和优化。

定义前缀和数组 $pref[x] = \sum_{j=0}^x dp[j]$（其中 $dp[j]=0$ 若 $j<0$）。那么

$$\sum_{b=L}^{R} dp[t-b] = \sum_{k=t-R}^{t-L} dp[k] = pref[t-L] - pref[t-R-1], $$

其中当 $t-R-1<0$ 时，$pref[t-R-1]$ 视为 $0$。

因此，我们可以用 $O(1)$ 时间计算每个 $t$ 的 $dp'[t]$，从而总转移时间为 $O(M)$。这样，处理完所有 $n$ 个数后，$F(d) = \sum_{t=0}^M dp[t]$。

注意：在实现时，我们使用滚动数组，只需维护当前 $dp$ 和下一个 $dp'$，空间复杂度 $O(M)$。

第四步：预处理莫比乌斯函数

莫比乌斯函数 $\mu(d)$ 可以通过线性筛在 $O(m)$ 时间内求出，用于后续求和。

第五步：总复杂度

对于每个 $d$，DP 的复杂度为 $O(n \cdot \lfloor m/d \rfloor)$。求和得

$$\sum_{d=1}^m n \cdot \frac{m}{d} = n m \sum_{d=1}^m \frac{1}{d} = O(n m \log m). $$

当 $n=50, m=10^5$ 时，约为 $50 \times 10^5 \times 12 = 6\times 10^7$ 次运算，加上取模操作，在 2 秒内是可行的。

实现细节

• 取模：所有运算在模 $998244353$ 下进行。
• 前缀和计算时注意负下标处理：令 $pref[-1]=0$。
• 因为 $dp$ 数组大小随 $M$ 变化，而 $M = \lfloor m/d \rfloor$ 可能为 0，此时 $F(d)=0$（因为 $M=0$ 时只有可能所有 $b_i=0$，但 $L_i\ge1$，故无解），可以直接跳过。
• 在累加答案时，注意 $\mu(d)$ 可能为负数，需调整为正（加 MOD 再取模）。

代码实现

下面给出标程，其中包含详细的注释。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXM = 100005;

int n, m;
int l[55], r[55];
int mu[MAXM];
vector<int> primes;
bool is_prime[MAXM];

// 线性筛求莫比乌斯函数
void sieve_mu(int N) {
    fill(is_prime, is_prime + N + 1, true);
    mu[1] = 1;
    for (int i = 2; i <= N; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (i * p > N) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
}

// 计算 F(d)
int solve(int d) {
    int M = m / d;
    vector<int> L(n), R(n);
    for (int i = 0; i < n; ++i) {
        L[i] = (l[i] + d - 1) / d;   // 上取整
        R[i] = r[i] / d;              // 下取整
        if (L[i] > R[i]) return 0;
    }
    vector<int> dp(M + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        // 前缀和
        vector<int> pref(M + 1, 0);
        pref[0] = dp[0];
        for (int s = 1; s <= M; ++s) {
            pref[s] = (pref[s - 1] + dp[s]) % MOD;
        }
        vector<int> ndp(M + 1, 0);
        for (int s = 0; s <= M; ++s) {
            int left = s - R[i];
            int right = s - L[i];
            if (right < 0) continue;
            int val = pref[right];
            if (left - 1 >= 0) val = (val - pref[left - 1] + MOD) % MOD;
            ndp[s] = val;
        }
        dp = ndp;
    }
    int res = 0;
    for (int s = 0; s <= M; ++s) res = (res + dp[s]) % MOD;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i];
    }
    sieve_mu(m);
    long long ans = 0;
    for (int d = 1; d <= m; ++d) {
        int cnt = solve(d);
        ans = (ans + 1LL * mu[d] * cnt) % MOD;
    }
    ans = (ans + MOD) % MOD;
    cout << ans << '\n';
    return 0;
}