Mocha and Stars

题意

给定 \(n,m\) ，问符合下定条件的数列有多少个：

对于\(a_i(1\le i\le n)\)，\(a_i\in [l_i,r_i]\cap \mathbb{Z}\)
\(\sum_{i=1}^ma_i\le m\)
\(\gcd(a_1,a_2,...a_n)=1\)

答案对 \(998\ 244\ 353\) 取模。

题解

倘若没有第二个条件，和这题就差不多了。第二个问题显然是个多重背包问题，所以我们把那题的代码稍微改一下，就能得出正确答案了。

每次要解决的子问题是这样的一个和原问题几乎一致的问题：

给定 \(n,m\) ，问符合下定条件的数列有多少个：

对于\(a_i(1\le i\le n)\)，\(a_i\in [l_i,r_i]\cap \mathbb{Z}\)
\(\sum_{i=1}^ma_i\le m\)

其中，\(\gcd(a_1,a_2,...,a_n)=d\)， \(d\) 是我们枚举的 \(\gcd\) 。容易发现，把这里的所有数全都除以 \(d\) ，就变成了这么个问题：

给定 \(n,m\) ，问符合下定条件的数列有多少个：

对于\(a_i(1\le i\le n)\)，\(a_i\in [\lceil l_i/d\rceil,\lfloor r_i/d \rfloor]\cap \mathbb{Z}\)
\(\sum_{i=1}^ma_i\le m/d\)

当成一个普通的前缀和优化的多重背包问题即可。

AC代码

#include <bits/stdc++.h>

#define IO ios::sync_with_stdio(NULL)

#define sc(z) scanf("%lld", &(z))

#define _ff(i, a, b) for (ll i = a; i <= b; ++i)

#define _rr(i, a, b) for (ll i = b; i >= a; --i)

#define _f(i, a, b) for (ll i = a; i < b; ++i)

#define _r(i, a, b) for (ll i = b - 1; i >= a; --i)

#define mkp make_pair

#define endl "\n"

#define pii pair<int,int>

#define fi first

#define se second

#define lowbit(x) x&(-x)

#define pb push_back

using namespace std;

typedef double db;

typedef long long ll;

typedef long double ld;

const int N = 50 + 5;

const ll M = 1e5 + 5;

const ll mod = 998244353;

const int inf = 1e9;

const double eps = 1e-9;

const double PI = acos(-1.0);

const pii NIL = {0,0};

int n, m;

ll l[N], r[N], dp[M], sum[M], f[M];

ll deal(ll d) {

    ll lim=m/d;

    f[0]=1;_ff(i,1,lim)f[i]=0;

    _ff(i,1,n){

        ll L=(l[i]+d-1)/d,R=r[i]/d;

        if(L>R)return 0;

        sum[0]=f[0];

        _ff(j,1,lim)sum[j]=(f[j]+sum[j-1])%mod;

        _ff(j,0,lim){

            if(j>R)f[j]=(sum[j-L]-sum[j-R-1]+mod)%mod;

            else if(j>=L)f[j]=sum[j-L];

            else f[j]=0;

        }

    }

    ll ans=0;

    _ff(i,1,lim)ans=(ans+f[i])%mod;

    return ans;

}

void solve() {

    cin>>n>>m;

    _ff(i,1,n)cin>>l[i]>>r[i];

    _rr(d,1,M){

        dp[d]=deal(d);

        for(int i=d+d;i<=M;i+=d)dp[d]=(dp[d]-dp[i]+mod)%mod;

    }

    cout<<dp[1]<<endl;

}

int main() {

    // IO;

    #ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);

    #endif // !ONLINE_JUDGE

    // pre();ll T; cin>>T;

    // _f(i,0,T) {

    //     // cout<<"Case "<<i+1<<": ";

    //     solve();

    // }

    solve();

    return 0;

}

Mocha and Stars的相关教程结束。