自动搬运

查看原文

来自洛谷，原作者为

	Engulf あまねく奇跡の始発点

搬运于2025-08-24 23:10:07，当前版本为作者最后更新于2025-08-18 21:25:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路参考：@chenwenmo 的题解。

单次询问 $O(n \ln n) \to \Theta(n)$

有个朴素的 $O(n \ln n)$ 暴力。

设 $a_i$ 表示窗沿 $i$ 最大积雪体积，暴力地枚举 $i$ 的因数转移。

取了多次 $\max$，是不是每次都是必要的？显然不是，打表可以发现，若记 $d_i$ 为 $i$ 的最大质因数，记 $j = \dfrac{i}{d_i}$（请记住 $j$ 的定义），那么 $i$ 一定由 $j$ 转移过来。

$$a_i = a_j + \left\lfloor \dfrac{n}{j} \right\rfloor - \dfrac{i}{j} + 1 $$

且

$$a_1 = 1$$

这样就有了单次询问 $\Theta(n)$ 的做法。

---

单次询问 $\Theta(n) \to O(1)$

要加速单次询问，要么是 $\log$，要么是预处理好 $O(1)$ 查询。

观察转移方程

$$a_i = \color{blue}a_j + \color{red}\left\lfloor \dfrac{n}{j} \right\rfloor \color{blue} - \dfrac{i}{j} + 1 $$

只有红色的部分与 $n$ 相关。可以把答案分成两部分，与 $n$ 无关的部分直接预处理好，计算前缀和，我们 重定义 $a$ 的转移

$$a_i = a_j - \dfrac{i}{j} + 1$$ $$a_1 = 1$$

再令

$$pre_n = \sum_{i = 1}^{n}a_i$$

就是蓝色部分的贡献。

接下来考虑计算红色部分的贡献，记为 $sum$。

如果连边 $j \to i$，会形成一棵树，转移就是一条到根的链。

那么红色部分的贡献就是

$$\sum_{j=1}^n (siz_j - 1)\left\lfloor \dfrac{n}{j} \right\rfloor $$

因为一个 $\left\lfloor \dfrac{n}{j} \right\rfloor$ 会贡献到子树内（不含 $j$）每一个 $i$。

交换求和顺序

$$\sum_{j=1}^n (siz_j - 1)\left\lfloor \dfrac{n}{j} \right\rfloor \ = \ \sum_{i=1}^n \sum_{j \ | \ i} siz_j - 1 $$

每次新加入一个 $i$，就相当于添加一个叶子。由于树高是 $\log$ 的，暴力跳父亲更新 $siz$。

我们递推维护 $sum$。在 $n-1\to n$ 的过程中，$sum$ 的变化量 $\Delta$ 由两部分组成。

• 由于 $siz$ 更新了，对于每个更新了的 $siz_k$，每个的增量是 $1$，增加贡献 $\left\lfloor\dfrac{\color{red}n-1}{k}\right\rfloor$，因为每个 $k$ 会在 $k$ 的倍数处都算一遍，红色部分是为了不重复计算；
• 另一部分是 $\sum\limits_{j \ | \ n} siz_j - 1$，这样的 $j$ 在 $2\cdot 10^6$ 的值域内是很少的，所以线性筛的时候记录每个数的最小质因数，$\log$ 时间分解质因数，dfs 就可以 $\Theta(d(n))$ 时间内找出所有 $n$ 的因数，$d(n)$ 表示 $n$ 的因数个数。

那么 $n$ 处的答案就是对应的 $sum + pre_n$。

预处理 $O(n \log n)$，单次询问 $O(1)$，总时间复杂度 $O(T + n\log n)$。

:::success[实现]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

const int N = 2e6 + 5;

int a[N];
int siz[N];

bool notprime[N];
vector<int> primes;
int d[N], mp[N];

ll pre[N];
ll ans[N];

vector<pii> divisors[N];

ll dfs(int u, vector<pii> &vec, int x) {
    if (u == vec.size()) return siz[x] - 1;
    ll res = 0;
    for (int i = 0; i <= vec[u].second; i++)
        res += dfs(u + 1, vec, x * pow(vec[u].first, i));
    return res;
}

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!notprime[i]) primes.emplace_back(i), d[i] = i, mp[i] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            notprime[primes[j] * i] = 1;
            d[primes[j] * i] = d[i];
            mp[primes[j] * i] = primes[j];
            if (i % primes[j] == 0) break;
        }
    }

    for (int i = 2; i <= n; i++) {
        int t = i;
        while (t > 1) {
            int lst = mp[t], cnt = 0;
            while (mp[t] == lst) cnt++, t /= mp[t];
            divisors[i].emplace_back(lst, cnt);
        }
    }

    d[1] = 1e9;
    a[1] = pre[1] = ans[1] = siz[1] = 1;
    ll sum = 0;
    for (int i = 2; i <= n; i++) {
        int j = i / d[i];
        a[i] = a[j] - i / j + 1;
        pre[i] = pre[i - 1] + a[i];
        for (int k = i; k; k = k / d[k])
            siz[k]++, sum += (i - 1) / k;
        sum += dfs(0, divisors[i], 1);
        ans[i] = pre[i] + sum;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve(N - 5);

    int tt;
    cin >> tt;
    while (tt--) {
        int n; cin >> n;
        cout << ans[n] << "\n";
    }
    return 0;
}

:::