E - Mocha and Stars

nn颗星星，每颗星星的亮度aia_i取值范围为[li,ri][l_i,r_i]，问满足∑ai≤m\sum a_i\le m同时gcd(a1,a2,...,an)=1gcd(a_1,a_2,...,a_n)=1的亮度取法有多少种。

首先考虑没有gcd限制的情况下的取法要怎么做、、最朴素的做法是枚举每个物品的aia_i取值，然后做背包，但是这样是O(nm2)O(nm^2)​的复杂度。考虑对于一个物品取值aia_i，一个固定容量jj是从j−aij-a_i转移过来的，那么对于取值在全部lil_i到rir_i的取值，固定容量是∑j−rij−lidpj\sum_{j-r_i}^{j-l_i}dp_j，所以可以记录前缀和，快速计算dpjdp_j

然后再来考虑没有∑ai≤m\sum a_i\le m​​​​​​限制的情况。我们设g(a1,a2,...,an)当gcd(a1,a2,...,an)=1时为1。当gcd(a1,a2,...,an)≠1时为0g(a_1,a_2,...,a_n)当gcd(a_1,a_2,...,a_n)=1 时为1 。当gcd(a_1,a_2,...,a_n)\ne1时为0​​​​​​​，那么可以列出以下式子

​ ∑a1=l1r1∑a2=l2r2⋯∑an=lnrn[gcd⁡(a1,a2,…,an)=1]g(a1,a2,…,an)=∑a1=l1r1∑a2=l2r2⋯∑an=lnrng(a1,a2,…,an)∑d∣gcd⁡(a1,a2,…,an)μ(d)=∑a1=l1r1∑a2=l2r2⋯∑an=lnrng(a1,a2,…,an)∑d∣a1,d∣a2,…,d∣anμ(d)=∑d=1Mμ(d)∑a1=⌈l1d⌉⌊r1d⌋∑a2=⌈l2d⌉⌊r2d⌋⋯∑an=⌈lnd⌉⌊rnd⌋g(a1d,a2d,…,and)\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) \\=\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) \\=\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) \\ =\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)​​​​​

再来考虑如何对这个式子加上限制。由于上式选择的是ai∗da_i*d​，那么限制可以表达为∑ai∗d≤m\sum a_i*d\le m​，将dd​除到右边即可得到∑ai≤⌊md⌋\sum a_i\le \lfloor\frac{m}{d}\rfloor​，用背包计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;
#define fast                          \
       ios_base::sync_with_stdio(false); \
       cin.tie(NULL);
typedef long long LL;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-3;
int l[N], r[N], n, m;
int dp[N], a[N], mu[N], flg[N], p[N], tot;
int solve(int val) {
    int res = 0, M = m / val;
    for (int i = 0; i <= M; i++) a[i] = 0;
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        int L = (l[i] + val - 1) / val, R = r[i] / val;
        if(L > R) return 0;
        for (int j = 0; j <= M; j++) 
            dp[j] = (a[j] + (j ? dp[j - 1] : 0)) % mod;
        for (int j = 0; j <= M; j++) 
            a[j] = ((j - L >= 0 ? dp[j - L] : 0) - (j - R - 1 >= 0 ? dp[j - R - 1] : 0) + mod) % mod; 
    }
    for (int i = 1; i <= M; i++) res = (res + a[i]) % mod;
    return res;
}
void getMu() {
    mu[1] = 1;
    for (int i = 2; i <= m; i++) {
        if(!flg[i]) p[++tot] = i, mu[i] = mod - 1;
        for (int j = 1; j <= tot && i * p[j] <= m; j++) {
            flg[i * p[j]] = 1;
            if(i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = (mod - mu[i]) % mod;
        }
    }
}
int main(){
    cin >> n >> m;
    getMu();
    int ans = 0;
    for (int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]);
    for (int i = 1; i <= m; i++) 
        ans = (ans + 1ll * mu[i] * solve(i)) % mod;
    printf("%d", ans);
    return 0;
}