题解：P11770 檐牙覆雪

Engulf · 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;
}

:::