题解 P1829 【[国家集训队]Crash的数字表格 / JZPTAB】

· · 题解

题目大意

给定 n,m，令

\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)≡x\pmod {20101009}

求最小的非负 x。

数据范围　1\leqslant n,m\leqslant 10^{7}

\begin{aligned}\end{aligned}

题解

开始推式子。

\begin{aligned}Ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{(i,j)}\\&=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{d}[(i,j)=d]\\&=\sum_{d=1}^{\min(n,m)}\sum_{i=1}^{\large\lfloor\frac nd\rfloor}\sum_{j=1}^{\large\lfloor\frac md\rfloor}\frac{d\cdot i\times d\cdot j}{d}[(i,j)=1]\\&=\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\large\lfloor\frac nd\rfloor}\sum_{j=1}^{\large\lfloor\frac md\rfloor}ij[(i,j)=1]\\&=\sum_{d=1}^{\min(n,m)}d\times \sum_{i=1}^{\large\lfloor\frac nd\rfloor}\sum_{j=1}^{\large\lfloor\frac md\rfloor}ij\sum_{k|i,k|j}\mu(k)\\&=\sum_{d=1}^{\min(n,m)}d\times \sum_{k=1}^{\large\lfloor\frac nd\rfloor}\mu(k)\sum_{k|i}^{i\leqslant {\large\lfloor\frac nd\rfloor}}i\sum_{k|j}^{j\leqslant {\large\lfloor\frac md\rfloor}}j\\&=\sum_{d=1}^{\min(n,m)}d\times \sum_{k=1}^{\large\lfloor\frac {\min(n,m)}d\rfloor}\mu(k)\left(\sum_{k|i}^{i\leqslant {\large\lfloor\frac nd\rfloor}}i\right)\left(\sum_{k|j}^{j\leqslant {\large\lfloor\frac md\rfloor}}j\right)\\&=\sum_{d=1}^{\min(n,m)}d\times \sum_{k=1}^{\large\lfloor\frac {\min(n,m)}d\rfloor}\mu(k)\left(\sum_{i=1}^{\large\lfloor\frac n{dk}\rfloor}ik\right)\left(\sum_{j=1}^{\large\lfloor\frac m{dk}\rfloor}jk\right)\\&=\sum_{d=1}^{\min(n,m)}d\times \sum_{k=1}^{\large\lfloor\frac {\min(n,m)}d\rfloor}k^2\mu(k)\left(\frac{\left(1+\Big\lfloor\dfrac n{dk}\Big\rfloor\right)\Big\lfloor\dfrac n{dk}\Big\rfloor}2\right)\left(\frac{\left(1+\Big\lfloor\dfrac m{dk}\Big\rfloor\right)\Big\lfloor\dfrac m{dk}\Big\rfloor}2\right)\end{aligned}

更换枚举项，枚举 T=kd，易得其上界为 n，并且 k|T，则有

\begin{aligned}Ans&=\sum_{T=1}^{\min(n,m)}\sum_{k|T}\frac Tk\times k^2\times \mu(k)\times {\left(\frac{\left(1+\Big\lfloor\dfrac n{T}\Big\rfloor\right)\Big\lfloor\dfrac n{T}\Big\rfloor}2\right)}{\left(\frac{\left(1+\Big\lfloor\dfrac m{T}\Big\rfloor\right)\Big\lfloor\dfrac m{T}\Big\rfloor}2\right)}\\&=\sum_{T=1}^{\min(n,m)}{\left(\frac{\left(1+\Big\lfloor\dfrac n{T}\Big\rfloor\right)\Big\lfloor\dfrac n{T}\Big\rfloor}2\right)}{\left(\frac{\left(1+\Big\lfloor\dfrac m{T}\Big\rfloor\right)\Big\lfloor\dfrac m{T}\Big\rfloor}2\right)}\sum_{k|T}k^2\times \mu(k)\times \frac Tk\end{aligned}

这里最好不要化简后面的

\sum_{k|T}k^2\times \mu(k)\times \frac Tk

最好直接把它转换为卷积

\begin{aligned}Ans&=\sum_{T=1}^n{\left(\frac{\left(1+\Big\lfloor\dfrac n{T}\Big\rfloor\right)\Big\lfloor\dfrac n{T}\Big\rfloor}2\right)}{\left(\frac{\left(1+\Big\lfloor\dfrac m{T}\Big\rfloor\right)\Big\lfloor\dfrac m{T}\Big\rfloor}2\right)}\Big((id^2\cdot\mu)*id\Big)(T)\end{aligned}

如果我们能线性筛出前面的 (id^2\cdot\mu)*id 就大功告成了。 这需要计算其三条特点：

\Big((id^2\cdot\mu)*id\Big)(1)=1 \Big((id^2\cdot\mu)*id\Big)(p)=p\cdot(1-p) \Big((id^2\cdot\mu)*id\Big)(p^k)=p^k\cdot(1-p)

证明：由于 p^0=1,p^1=p，因而我们只需要证明第三条性质成立即可。

\begin{aligned}\Big((id^2\cdot\mu)*id\Big)(p^k)&=\sum_{d|p^k} (id^2\cdot\mu)(d)\times id\left(\frac{p^k}{d}\right)\\&=p^k\times \sum_{d|p^k} d\cdot\mu(d)\\&=p^k\times \sum_{t=0}^k p^t\cdot\mu(p^t)\\&=p^k\times \left(p^0\cdot\mu(p^0)+p^1\cdot\mu(p^1)+\sum_{t=2}^kp^t\cdot\mu(p^t)\right)\\&=p^k\times \left(1-p+\sum_{t=2}^kp^t\times0\right)\\&=p^k\cdot\left(1-p\right)\end{aligned}

至此，我们能够在 T(k)=\Theta(1) 的时间内求出上面三种位置的函数值，因此，我们可以线性筛了。

总时间复杂度进一步降低到 T(n)=\Theta(n+\sqrt n)。

但这样常数有些大，会不会有风险？

考虑杜教筛。

只要求出函数 \Big((id^2\cdot \mu)*id\Big) 的前缀和即可。因此考虑取 g=id。

等等！

为什么要考虑 g=id？为了让后续的 乱猜 更方便？如果 g=id 能做到些什么的话，为什么里面那个 id 不能做到？ 考虑到卷积有交换律，我们可以忽略后面那个 *id 而直接考虑前面的 (id^2\cdot \mu)，很容易发现，对于这个用点乘得到函数只需要取 g=id^2 即可。

\begin{aligned}\bigg(\Big((id^2\cdot \mu)*id\Big)*id^2\bigg)(n)&=\bigg(\Big((id^2\cdot \mu)*id^2\Big)*id\bigg)(n)\\&=\sum_{d|n}\Big((id^2\cdot \mu)*id^2\Big)(d)\times\frac nd\\&=\sum_{d|n}\sum_{k|d}k^2\cdot \mu(k)\times\frac {d^2}{k^2}\times \frac nd\\&=n\sum_{d|n}d\sum_{k|d}\mu(k)\\&=n\sum_{d|n}d[d=1]\\&=n\\&=id(n)\end{aligned}

的确是个让人省心的函数。 因而有

\begin{aligned}n&=\bigg(\Big((id^2\cdot \mu)*id\Big)*id^2\bigg)(n)\\&=\sum_{d|n}\Big((id^2\cdot \mu)*id\Big)(d)\times \frac{n^2}{d^2}\\&=\sum_{d|n,d\not=n}\Big((id^2\cdot \mu)*id\Big)(d)\times \frac{n^2}{d^2}+\Big((id^2\cdot \mu)*id\Big)(n)\end{aligned}

移项，得

\Big((id^2\cdot \mu)*id\Big)(n)=n-\sum_{d|n,d\not=n}\Big((id^2\cdot \mu)*id\Big)(d)\times \frac{n^2}{d^2}

求和

\begin{aligned}\text{Sum}_{(id^2\cdot \mu)*id}(n)&=\sum_{i=1}^n\Big((id^2\cdot \mu)*id\Big)(i)\\&=\sum_{i=1}^ni-\sum_{i=1}^n\sum_{d|i,d\not=i}\Big((id^2\cdot \mu)*id\Big)(d)\times \frac{i^2}{d^2}\\&=\frac{(1+n)n}2-\sum_{k=2}^n\sum_{d=1}^{\large\lfloor\frac nk\rfloor}\Big((id^2\cdot \mu)*id\Big)(d)\times\frac{k^2d^2}{d^2}\\&=\frac{(1+n)n}2-\sum_{k=2}^nk^2\times \text{Sum}_{(id^2\cdot \mu)*id}(n)\left(\Big\lfloor\frac nk\Big\rfloor\right)\end{aligned}

递归除法分块处理即可，时间复杂度为 T(n)=\Theta(n^{\frac 34}) 前面莫比乌斯反演的部分除法分块处理，总时间复杂度仍然为 T(n)=\Theta(n^{\frac 34})。 再把前面 n\frac 23 线性筛出来，时间复杂度就降低到了 \Theta(n^{\frac 23})

Accepted 100 用时: 470ms 内存: 13828KB

#include<bits/stdc++.h>
using namespace std;
#define maxn 406415
const long long mod=20101009;
long long inv_2=500000004;
long long inv_6=166666668;
long long low[maxn],f[maxn],pri[maxn],vis[maxn],s[maxn];
void sieve(long long n){
    memset(vis,0,sizeof vis);
    long long tot=0;
    vis[1]=low[1]=f[1]=1;
    for (long long i=2;i<=n;i++)
    {
        if(!vis[i]) low[i]=pri[++tot]=i,f[i]=(i-(i*i)%mod+mod)%mod;
        for (long long j=1;j<=tot&&i*pri[j]<=n;j++)
        {
            vis[i*pri[j]]=1;
            if (i%pri[j]==0)
            {
                low[i*pri[j]]=low[i]*pri[j];
                if (low[i]==i)
                    f[i*pri[j]]=((((1-pri[j])*i+mod)%mod)*pri[j]+mod)%mod;
                else
                    f[i*pri[j]]=(f[i/low[i]]*f[low[i]*pri[j]]+mod)%mod;
                break;
            }
            low[i*pri[j]]=pri[j];
            f[i*pri[j]]=(f[i]*f[pri[j]])%mod;
        }
    }
    for(int i=1;i<=n;i++)
        s[i]=(s[i-1]+f[i]+mod)%mod;
}
long long ft_1(long long a){
    long long t=a%mod;
    return ((((1+(t))*(t))%mod)*inv_2)%mod;
}
long long ft_2(long long a){
    long long t=a%mod;
    return (((t*(t+1)%mod)*(2*t+1)%mod)*inv_6)%mod;
}
map<long long,long long> Sf;
long long S(long long n){
    if(n<=maxn-10) return s[n];
    {   map<long long,long long>::iterator t=Sf.find(n);
        if(t!=Sf.end()) return t->second;   }
    long long ans=ft_1(n);
    for(long long l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        ans-=S(n/l)*(ft_2(r)-ft_2(l-1))%mod;
        ans=(ans+mod)%mod;
    } return Sf[n]=ans;
}
void main2(long long n,long long m){
    long long ans=0;
    long long len=min(n,m);
    for(long long l=1,r;l<=len;l=r+1){
        r=min(n/(n/l),m/(m/l));
        if(r>n) r=n;
        ans+=ft_1(n/l)*ft_1(m/l)%mod*(S(r)-S(l-1))%mod;
        ans=(ans+mod)%mod;
    } printf("%lld",ans); 
}
long long pow_t(long long a,long long b){
    if(b==1) return a%mod;
    long long t=pow_t(a,b/2);
    if((b&1)==0) return t*t%mod;
    return t*t%mod*a%mod;
}
int main(){
    inv_2=pow_t(2,mod-2);
    inv_6=pow_t(6,mod-2);
    sieve(maxn-10);
    long long n,m,ans=0;
    scanf("%lld%lld",&n,&m);
    main2(n,m);
    return 0;
}

记得记忆化，记得记忆化，记得记忆化……别问我怎么知道的。 修改一下模数和规模，本代码还可以通过其增强版。

PS：面对luogu的Latex公式不能换行毫无还手之力，改到自闭……

附录：公式对齐方法

$$\begin{aligned}
T&=\sum_{i=1}^ni\\
&=\frac{n(1+n)}{2}\\
&=\frac 12\left(n+n^2\right)
\end{aligned}$$

但是luogu的公式必须写在同一行中，因此应该这么写

$$\begin{aligned}T&=\sum_{i=1}^ni\\&=\frac{n(1+n)}{2}\\&=\frac 12\left(n+n^2\right)\end{aligned}$$

效果：

\begin{aligned}T&=\sum_{i=1}^ni\\&=\frac{n(1+n)}{2}\\&=\frac 12\left(n+n^2\right)\end{aligned}