E. Mocha and Stars_牛客博客

如果求解： ${\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)=1]}$

根据莫比乌斯的一般套路，很容易想到如下转化：

${\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}\varepsilon(gcd(a_1,a_2,...,a_n))}$

$={\sum_{a_1=l_1}^{r_1}\sum_{a_2=l_2}^{r_2}...\sum_{a_n=l_n}^{r_n}\sum_{d|gcd(a_1,a_2,...,a_n)}\mu(d)}$

$={\sum_{d=1}\mu(d)\sum_{a_1=l_1}^{r_1}[d|a_1]\sum_{a_2=l_2}^{r_2}[d|a_2]...\sum_{a_n=l_n}^{r_n}[d|a_n]}$

$={\sum_{d=1}\mu(d)\sum_{a_1=⌊\frac{l_1}{d}⌋}^{⌊\frac{r_1}{d}⌋}\sum_{a_2=⌊\frac{l_2}{d}⌋}^{⌊\frac{r_2}{d}⌋}...\sum_{a_n=⌊\frac{l_n}{d}⌋}^{⌊\frac{r_n}{d}⌋}}$

即将原式转化为莫比乌斯函数后交换求和顺序。

考虑问题二的限制，有：

${\sum_{d=1}\mu(d)\sum_{a_1=l_1}^{r_1}[d|a_1]\sum_{a_2=l_2}^{r_2}[d|a_2]...\sum_{a_n=l_n}^{r_n}[d|a_n][a_1+a_2+...+a_n<=m]}$

$={\sum_{d=1}\mu(d)\sum_{a_1=⌊\frac{l_1}{d}⌋}^{⌊\frac{r_1}{d}⌋}\sum_{a_2=⌊\frac{l_2}{d}⌋}^{⌊\frac{r_2}{d}⌋}...\sum_{a_n=⌊\frac{l_n}{d}⌋}^{⌊\frac{r_n}{d}⌋}[a_1+a_2+...+a_n<=\frac{m}{d}]}$

${\sum_{a_1=⌊\frac{l_1}{d}⌋}^{⌊\frac{r_1}{d}⌋}\sum_{a_2=⌊\frac{l_2}{d}⌋}^{⌊\frac{r_2}{d}⌋}...\sum_{a_n=⌊\frac{l_n}{d}⌋}^{⌊\frac{r_n}{d}⌋}[a_1+a_2+...+a_n<=\frac{m}{d}]}$ ，这部分就是个背包问题，假设 ${dp[i][j]}$ 表示前 ${i}$ 个数相加和为 ${j}$ 的方案数。

那么转移方程有： ${dp[i][j]=\sum_{k=l_i}^{r_i}dp[i-1][j-k]}$

直接转移复杂度是 ${O(nm^2)}$ 的，注意到等式右边可以用前缀和维护，令 ${sum[i][j]=\sum_{k=0}^{j}dp[i][k]}$ ，则有：

${dp[i][j]=sum[i-1][j-l_i]-sum[i-1][j-r_i-1]}$

显然只要先用 ${sum}$ 更新 ${dp}$ ，再用 ${dp}$ 更新 ${sum}$ 就可以把第一维去掉，复杂度 ${O(mn)}$ 。

很显然，我们只要枚举 ${d|gcd(a_1,a_2,...,a_n)}$ ，然后跑一遍背包，总的复杂度就是 ${O(mn(\frac{1}{1}+\frac{1}{2}+...+\frac{1}{m})*m)}$ ，近似等于 ${O(mn\ lnm)}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7,mod=998244353;
int mu[maxn],L[55],R[55],l[55],r[55];
ll sum[maxn],f[maxn];
int main() {
    int n,m,tot;
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>L[i]>>R[i];
    mu[1]=1;
    for(int i=1;i<=m;++i)
    for(int j=i+i;j<=m;j+=i) mu[j]-=mu[i];
    ll ans(0);
    for(int d=1;d<=m;++d) {
        if(!mu[d]) continue;
        for(int i=1;i<=n;++i) l[i]=(L[i]+d-1)/d,r[i]=R[i]/d;
        tot=m/d;
        for(int i=0;i<=tot;++i) sum[i]=1;
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=tot;++j) f[j]=0;
            for(int j=l[i];j<=tot;++j) {
                f[j]=sum[j-l[i]];
                if(j-r[i]-1>=0) f[j]=(f[j]-sum[j-r[i]-1]+mod)%mod;
            }
            sum[0]=0;
            for(int j=1;j<=tot;++j) sum[j]=(sum[j-1]+f[j])%mod;
        }
        ans=(ans+mu[d]*sum[tot])%mod;
    }
    cout<<(ans+mod)%mod<<'\n';
}