题解 CF1559E

· · 题解

求出满足以下条件的整数数组 a 个数

  • 长度为 n
  • 和不超过 m
  • 最大公约数是 1
  • a_i \in [l_i, r_i]

如果没有 \gcd 的限制那么就是一个简单背包，容易想到用前缀和优化，时间复杂度就变成了 nm。

主要的问题还是出在这个 \gcd 如何处理，容易想到要用容斥做，可是我却不知道应该怎样去容斥，在分解质因数的思路上花费了很多的时间，但是遗憾的是这是一条死路。
主要是没有想到一个容斥的小 trick。

在处理 \gcd 为 x 的问题时，可以倒着枚举一个 i，设 ans_i 是 \gcd 恰好为 i 的方案数，f_i 为 \gcd 是 i 的倍数的方案数。

那么就可以用 ans_g = f_g - \sum_{g|i} ans_i 来求解。

用这个方法结合原来的背包，先用背包求出 f，然后再进行下面的容斥就可以了。 具体地，设 f_{i, j} 是前 i 个和不超过 j\times g 的方案数，f_{i, j} = \sum f_{i-1, k}， k 是枚举之前的和能到这里的，l 和 r 都要除以 g 处理，然后前缀和优化即可。初始化是 f_{0, i} = 1，因为是前缀和，每次叠了个 1，实际上只有 f_{0, 0} = 1 目标状态是 f_{n, m/g}。

但是赛场上我还是遇到了一个小问题改变了我思考的方向，在考虑容斥之前考虑求总数的时候觉得这个复杂度是 nm^2 的无法通过，所以放弃了这个方向的思考，转而去想着分解出来的质数出不出现的问题。
实际上这个复杂度根本就是 O(nm \ln m) 的，因为除以了 g 之后复杂度变成了调和级数。

#include <iostream>
#include <algorithm>
#define int long long
const int N = 55, M = 100005, P = 998244353;
int n, m, l[N], r[N], f[N][M], ans[M];
signed main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) std::cin >> l[i] >> r[i];
    for (int g = m/n; g >= 1; g--) {
        for (int i = 0; i <= n; i++)    
            for (int j = 0; j <= m/g+1; j++) f[i][j] = 0;
        for (int j = 0; j <= m/g+1; j++) f[0][j] = 1;
        for (int i = 1; i <= n; i++) {
            int L = (l[i]+g-1)/g, R = r[i]/g;
            for (int a = L; a <= m/g+1; a++) {
                int cl = std::max(a-R, 0ll), cr = a-L;
                if (cl > cr) f[i][a] = 0;
                else f[i][a] = (f[i-1][cr] - (cl ? f[i-1][cl-1] : 0) + P) % P;
                if (a > 0) f[i][a] = (f[i][a] + f[i][a-1]) % P;
            }
        }
        ans[g] = f[n][m/g];
        for (int i = 2*g; i <= m; i += g) ans[g] = (ans[g] - ans[i] + P) % P;
    }
    std::cout << ans[1];
}