[yLCPC2024] G. 系ぎて

gyyyyx · 2024-03-09 21:17:39 · 题解

题面

代码：

首先考虑二维的情况。

发现对于每一个 i\in[1,n]，对所有 1\sim n 中 i 的倍数都有 1 的贡献。

答案即为 \sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor。

整除分块可解。

接着拓展到三维。

显然如果确定了 i，那问题就变成了二维的。

也就是说，对于每一个 i，对答案的贡献为 \sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor\frac{n}{ij}\rfloor。

直接整除分块套整除分块。

但提交后发现过不了。

有一个很简单的想法：令 f_m=\sum\limits_{i=1}^m\lfloor\frac{m}{j}\rfloor，先提前求出一些 f_i 的值，然后再去跑整除分块。

由于你会发现当整除分块跑的一定程度的时候，\lfloor\frac{n}{i}\rfloor 的密度是很大的。

也就是说基本上所有的 f_i 我们都是能用上的。

理论上应该是挺快的。

现在的瓶颈就在于如何快速求 f_i。

可惜赛时没想出来怎么求。

发现对于一个 i，对 f_1,f_2,\cdots,f_{i-1} 的贡献为 0，对 f_i,f_{i+1},\cdots,f_{2i-1} 的贡献为 1，对 f_{2i},f_{2i+1},\cdots,f_{3i-1} 的贡献为 2。

也就是对于任意 i 和 j，i 对 f_{ij},f_{ij+1},\cdots,f_{i(j+1)-1} 的贡献为 j。

我们可以用差分来维护。

时间复杂度是我们很熟悉的调和级数，大约是 O(m\log m) 的。

最后就是大约要算多少个 f_i。

所以就算了 10^5 个，开个 O2 跑得还是挺快的。

@Nz 给出了我的总时间复杂度是 O(m\log m+n^{\frac{3}{4}})。

代码：

#include<bits/stdc++.h>
#define LL unsigned long long
#define M 1000000
using namespace std;
LL n,sum,ans;
LL f[M+5];
int main(){
    for(int i(1);i<=M;++i)
        for(int j(1);j<=M/i;++j){
            f[i*j]+=j;
            if(j+1<=M/i) f[i*(j+1)]-=j;
        }
    for(int i(1);i<=M;++i) f[i]+=f[i-1];
    scanf("%llu",&n);
    LL l(1),r,k;
    while(l<=n){
        k=n/l;r=n/k;
        if(k<=M) ans+=f[k]*(r-l+1);
        else{
            LL _l(1),_r,res(0);
            while(_l<=k){
                _r=k/(k/_l);
                res+=(_r-_l+1)*(k/_l);
                _l=_r+1;
            }
            ans+=res*(r-l+1);
        }
        l=r+1;
    }
    printf("%llu\n",ans);
    return 0;
}