题解：P15765 [JAG 2025 Summer Camp #1] Sum of Floor(N/ij)

· · 题解

update：时间复杂度还是有锅，麻烦管理了……

update：被指出时间复杂度分析错误，修改后重交。

这道题显然可以整除分块套整除分块，但是时间复杂度 O(Tn^{\frac{3}{4}})，显然不可过。好像有人过了？

所以我们考虑将式子变形。对于原式，记 k=ij，我们发现当且仅当 k\leq n 的时候有贡献。于是我们可以考虑枚举 k，这样就可以得到下面的这个式子：

\sum^{n}_{k=1}\left\lfloor\frac{n}{k}\right\rfloor d(k)

前面的一部分显然，d(k) 是这个 k 会被选到的次数，即 k 的正约数个数。直接用线性筛预处理是 O(n+T\sqrt{n}) 的，并不优秀。于是我们考虑摊平复杂度。

我们用线性筛预处理 B 个数，那么就可以得出如下的时间复杂度：

首先，预处理是 O(B)。对于 n>B 的情况，我们可以使用整除分块来求 \sum^{n}_{i=1}d(i)（这个想必大家都会吧，可以转化为 \sum^{n}_{i=1}\lfloor\frac{n}{i}\rfloor），这个对于单点求值是 O(\sqrt{n}) 的。那么，总共会求多少次单点呢？注意到我们的每一个 n，在整除分块中，对于 n>B 总共会贡献 \frac{n}{B} 次，然后我们可以使用一个哈希来存储已经求过的前缀和，就不会反复求了，所以时间复杂度是 O(\frac{n}{B}\sqrt n) 的。一共要求 T 次，所以总时间复杂度是 O(T\frac{n}{B}\sqrt n) 的。

但是由于使用了记忆化严重跑不满，并且随着 T 的增加越来越跑不满，应该是有更严格的上界的。

取 B=\sqrt T n^{\frac{3}{4}} 可以做到最优时间复杂度 O(\sqrt Tn^{\frac{3}{4}}+T\sqrt n)，有一个根号是因为每一次查询的时候都要整除分块。可以通过加强版：https://www.luogu.com.cn/problem/U684999，虽然好像跑的比造数据的人慢……

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e7 + 5;
unordered_map<int, int> sd; 
bool isp[N];
int t, n, prime[N], cnt[N], d[N], tp;

void sieve(int n) {
    d[1] = 1;
    for(int i = 2; i <= n; i ++ ) {
        if(!isp[i]) prime[ ++ tp] = i, d[i] = 2, cnt[i] = 1;
        for(int j = 1; j <= tp && i * prime[j] <= n; j ++ ) {
            isp[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                cnt[i * prime[j]] = cnt[i] + 1;
                d[i * prime[j]] = d[i] / (cnt[i] + 1) * (cnt[i] + 2);
                break;
            } else {
                cnt[i * prime[j]] = 1;
                d[i * prime[j]] = d[i] * d[prime[j]];
            } 
        }
    }
    for(int i = 1; i <= n; i ++ ) d[i] += d[i - 1];
}

int getd(int x) {
    if(x <= N - 5) return d[x];
    if(sd[x]) return sd[x];
    int ans = 0;
    for(int i = 1, j; i <= x; i = j + 1)
        j = x / (x / i), ans += (x / i) * (j - i + 1);
    return sd[x] = ans;
}

int solve(int x) {
    int ans = 0;
    for(int i = 1, j; i <= x; i = j + 1)
        j = x / (x / i), ans += (x / i) * (getd(j) - getd(i - 1));
    return ans;
} 

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> t;
    sieve(N - 5);
    while(t -- ) {
        cin >> n;
        cout << solve(n) << endl;
    }
    return 0;
}