我们支持使用新型的大炮打蚊子技术

· · 题解

:::warning[注意]{open}

本题解涉及的算法难度为 NOI/NOI+/CTSC。请谨慎参考。

:::

目前的最优解，Submission。

题意

给定 N，求：

\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\left\lfloor \frac{N}{ij} \right\rfloor.

多测，T 组数据。T \le 100，N \le 10^9。

思路

简单推式子：

\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\left\lfloor \frac{N}{ij} \right\rfloor &= \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\left\lfloor \frac{\left\lfloor \frac{N}{i} \right\rfloor}{j} \right\rfloor\\ &= \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{\left\lfloor \frac{N}{i} \right\rfloor}\left\lfloor \frac{\left\lfloor \frac{N}{i} \right\rfloor}{j} \right\rfloor\\ &= \sum\limits_{i=1}^{N}\sum\limits_{j=1}^{\left\lfloor \frac{N}{i} \right\rfloor}\sigma_0(j).\\ \end{aligned}

设 S_1(n) = \displaystyle\sum\limits_{i=1}^{n}\sigma_0(i)，则答案为：

\sum\limits_{i=1}^{N}S_1\left( \left\lfloor \frac{N}{i} \right\rfloor \right).

考虑用 DIVCNT1 的方法计算 S_1(n)，时间复杂度为 \mathcal{O}(n^{\frac{1}{3}} \log n)。

若在外层直接整除分块，内层用 DIVCNT1 的方法计算 \displaystyle S_1\left( \left\lfloor \frac{N}{i} \right\rfloor \right)，则时间复杂度为：

W(N) &= \sum\limits_{k \in S} \mathcal{O} \left( k^{\frac{1}{3}} \log k \right)\\ &= \left( \sum\limits_{k \in S} \mathcal{O} \left( k^{\frac{1}{3}} \right) \right) \mathcal{O} \left( \log N \right). \end{aligned}

其中 S 为整除分块的取值集合。设 \displaystyle \sum\limits_{k \in S} \mathcal{O} \left( k^{\frac{1}{3}} \right) = W_0(N)，则：

W_0(N)&= \sum\limits_{k=1}^{\sqrt{N}} \mathcal{O} \left( k^{\frac{1}{3}} \right) + \sum\limits_{k=1}^{\sqrt{N}} \mathcal{O} \left( \left( \frac{N}{k} \right)^{\frac{1}{3}} \right)\\ &= \mathcal{O} \left( \int_{1}^{\sqrt{N}} x^{\frac{1}{3}} \,\mathrm{d}x \right) + \mathcal{O} \left( N^{\frac{1}{3}} \int_{1}^{\sqrt{N}} x^{-\frac{1}{3}} \,\mathrm{d}x \right)\\ &= \mathcal{O} \left( N^{\frac{2}{3}} \right). \end{aligned}

故时间复杂度为 \mathcal{O} \left( N^{\frac{2}{3}} \log N \right)。

总复杂度为 \mathcal{O} \left( TN^{\frac{2}{3}} \log N \right)。

考虑优化。

设 \displaystyle\mathrm{Ans}(n) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\left\lfloor \frac{n}{ij} \right\rfloor。

考虑预处理出一部分 S_0(n) 和 \mathrm{Ans}(n) 以平衡复杂度。

令预处理阈值 M = \Theta \left( N_{\text{m}}^{\frac{2}{3}} \right)，其中 N_{\text{m}} = 10^9。预处理出 M 以内的 S_1(n) 与 \mathrm{Ans}(n)。

考虑每组数据中 N 的大小。

若 N \le M，直接出答案。

若 N > M，答案可以分为两部分计算：

\mathrm{Ans}(N) = \sum\limits_{i=1}^{\left\lfloor \frac{N}{M} \right\rfloor} S_1\left( \left\lfloor \frac{N}{i} \right\rfloor \right) + \sum\limits_{i=\left\lfloor \frac{N}{M} \right\rfloor + 1}^{N} S_1\left( \left\lfloor \frac{N}{i} \right\rfloor \right).

注意到第二部分中 \displaystyle \left\lfloor \frac{N}{i} \right\rfloor \le M，因此单个 \displaystyle S_1\left( \left\lfloor \frac{N}{i} \right\rfloor \right) 可 \mathcal{O}(1) 得出。

第二部分利用数论分块计算即可，复杂度为 \mathcal{O} \left( \sqrt{N} \right)。

第一部分用 DIVCNT1 的方法计算，其时间复杂度为：

W_1(N) &= \sum\limits_{k=1}^{\left\lfloor \frac{N}{M} \right\rfloor} \mathcal{O} \left( \left( \frac{N}{k} \right)^{\frac{1}{3}} \log N\right)\\ &= \mathcal{O}\left( N^{\frac{1}{3}} \log N \int_{1}^{\frac{N}{M}} x^{-\frac{1}{3}} \,\mathrm{d}x \right)\\ &= \mathcal{O}\left( N^{\frac{1}{3}} \log N \left( \frac{N}{M} \right)^{\frac{2}{3}} \right)\\ &= \mathcal{O}\left( N^{\frac{1}{3}} \log N \left( N^{\frac{2}{9}} \right) \right)\\ &= \mathcal{O}\left( N^{\frac{5}{9}} \log N \right). \end{aligned}

预处理复杂度为 \mathcal{O}\left( M \log M \right) = \mathcal{O}\left( N^{\frac{2}{3}} \log N \right)。

总复杂度为 \mathcal{O}\left( N^{\frac{2}{3}} \log N + TN^{\frac{5}{9}} \log N \right)。

upd：令 M = \Theta \left( \left( TN_{\text{m}} \right) ^{\frac{3}{5}} \right)，可以取到理论最优复杂度 \mathcal{O} \left( (TN)^{\frac{3}{5}} \log N \right)，但是跑的并不快。

Code

#include<bits/stdc++.h>
#define ll long long

const int M=2e6+10;

const int _M=1.5e5+10;

using namespace std;

int T;

int n,m=2e6;

ll ans;

char k[M];

int sig_0[M];

int cnt,p[_M];

bitset<M>vis;

int Ans[M];

unordered_map<int,ll>mp;

namespace DIVCNT1{
    inline ll calc_sig_0(int n){
        // 参见 DIVCNT1 
    }
}

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
    return ret*f;
}

inline void _init(){
    sig_0[1]=1;
    for(int i(2);i<=m;++i){
        if(!vis[i]){
            p[++cnt]=i;
            k[i]=1;
            sig_0[i]=2;
        }
        for(int j(1);j<=cnt&&i*p[j]<=m;++j){
            vis[i*p[j]]=1;
            if(i%p[j]){
                k[i*p[j]]=1;
                sig_0[i*p[j]]=sig_0[i]*sig_0[p[j]];
            }
            else{
                k[i*p[j]]=k[i]+1;
                sig_0[i*p[j]]=sig_0[i]/(k[i]+1)*(k[i]+2); 
                break;
            }
        }
    }
    for(int i(1);i<=m;++i){
        for(int j(i);j<=m;j+=i){
            Ans[j]+=sig_0[i];
        }
    }
    for(int i(1);i<=m;++i)sig_0[i]+=sig_0[i-1];
    for(int i(1);i<=m;++i)Ans[i]+=Ans[i-1];
}

inline void _solve(){
    n=read(),ans=0;
    if(n<=m){
        printf("%d\n",Ans[n]);
        return;
    }
    int _n=n/m;
    for(int i(1);i<=_n;++i)ans+=DIVCNT1::calc_sig_0(n/i);
    for(int l(_n+1),r;l<=n;l=r+1){
        r=n/(n/l);
        ans+=sig_0[n/l]*(r-l+1);
    }
    printf("%lld\n",ans);
}

signed main(){
    _init();
    T=read();
    while(T--)_solve();
    return 0;
}