一共有 n 级窗沿，从高到低编号，最高层编号为 1，最底层编号为 n。每一级窗沿上的积雪都可以看作包含若干雪团的可重集合，一开始，第 1 级窗沿上有一团体积为 1 的雪，其他窗沿上没有任何积雪。积雪产生了 n 次变换。
第 i 次变换中，第 i 级窗沿上的每一团雪都会被卷起，所有编号是 i 的整数倍（不包括i 自身）的窗沿都会接收到新的积雪。具体地，设一团被卷起的雪体积为 V，则在上述窗沿中，编号最大者会得到一团体积为 V+1 的积雪，次大者会得到一团体积为 V+2 的积雪，以此类推。最后，被卷起的雪团回到第 i 级窗沿，也就是说本次变换后，第 i 级窗沿上的积雪没有任何变化。
求出 n 次变换之后，每级窗沿上体积最大的一团雪的总体积是多少。
### 题解
首先，$i$ 的最大堆一定是由它的某个约数 $j$ 的**最大堆**产生的。这是显然的，因为 $j$ 的所有堆都是加上一个**相同的量**贡献给 $i$。
设 $f(i)$ 表示最后 $i$ 的最大堆有多少单位雪，转移有，$f(i) = \max\limits_{j\mid i}\{f(j) + \lfloor\frac{n}{j}\rfloor - \frac{i}{j}+1\}$。就是 $i$ 的某个约数 $j$ 的最大堆，加上 $i$ 是 $j$ 的 $n$ 以内的倒数（shu，第三声）第几个倍数。
然后直接转移是 $O(Tn\log n)$ 的。
然后我赛时通过打表发现，对于任意 $i$ 的转移点 $j$，是和 $n$ 无关的，也就是不变的。
> 证明：
>
> 考虑有 $i<j<k$ 满足 $i\mid j$ 且 $j\mid k$，因为 $i$ 的所有约数提供给它的雪，肯定也会提供给 $j$，因此 $f(j)>f(i)$，所以 $f(k)$ 肯定由 $f(j)$ 转移。
>
> 那么这时候就有 $f(i)=\max\limits_{p\mid i,p\in prime} f(\frac{i}{p}) + \lfloor\frac{n}{\frac{i}{p}}\rfloor - p+1$。
>
> 由于 $p$ 是质数，因此无论 $f(i)$ 当前选择了哪个 $p$，后面那部分 $-p+1$ 肯定会以 $\sum\limits_{p\mid i,p\in prime} -p+1$ 的形式累加到 $f(i)$ 中。
>
> 那么现在就要求 $\lfloor\frac{n}{\frac{i}{p}}\rfloor$ 最大，显然 $p$ 取 $i$ 的最大质因子即可。
>
> 因此所有 $f(i)$ 的转移点为 $i$ 除以其最大质因子。
于是我们可以预处理出所有转移点，即可做到 $O(Tn)$。
将 $i$ 的转移点记为 $p_i$，$f(i)=f(p_i)+\lfloor\frac{n}{p_i}\rfloor - \frac{i}{p_i}+1$，我们每次都要重新算一遍，就是因为转移方程里有一个 $\lfloor\frac{n}{p_i}\rfloor$。
能不能直接把转移方程变为 $f(i)=f(p_i)- \frac{i}{p_i}+1$，预处理出 $sum_n=\sum\limits_{i=1}^{n}f(i)$，然后对于每个 $n$ 直接计算多出来的 $\lfloor\frac{n}{p_i}\rfloor$ 的总贡献呢？
如果我们从 $p_i$ 到 $i$ 连一条有向边，那么整个图就构成一棵以 $1$ 为根的内向树。那么容易发现，对于 $n$，总答案会在 $sum_n$ 的基础上，增加 $\sum\limits_{i=1}^{n} h_i \times \frac{n}{i}$，其中 $h_i=siz_i-1$，$siz$ 是子树大小。
也就是对于每个 $n$，答案是 $sum_n + \sum\limits_{i=1}^{n} h_i \times \frac{n}{i}$，
但是注意，上面说到的那棵内向树，只能是由 $\le n$ 的点构成的，也就是我们还是有 $n$ 这个限制。
变换一下，$\sum\limits_{i=1}^{n} h_i \times \frac{n}{i} = \sum\limits_{i=1}^{n}\sum\limits_{j\mid i} h_j$，
如果我们已经计算出了 $n-1$ 的答案，考虑在 $n$ 的时候，我们可以不断从 $n$ 跳 $p_n$，然后把除了 $n$ 以外，路径上的所有 $h_i$ 都加 $1$。由于跳的次数为 $O(\log n)$，那么这样就可以维护所有 $h_i$。
然后我们要算的是 $\sum\limits_{i=1}^{n}\sum\limits_{j\mid i} h_j$ 这个式子在 $n-1\to n$ 时的增量，这个增量分为两部分。
- 对于上面说到的加了 $1$ 的 $h_i$，增量会增加 $\lfloor\frac{n-1}{i}\rfloor$，这里 $n-1$ 是为了避免和下面的情况重复计算。
- 然后增量还会增加 $\sum\limits_{j\mid n}h_j$。这里必须在 $O(约数个数)$ 的时间内遍历 $n$ 的所有约数，可以分解质因数，然后 DFS 枚举。
还要记得更新 $sum$，$sum_n = sum_{n-1} + f(n)$，（这里 $f$ 的转移方程是改变之后的）。
最后可以离线处理，也可以算出所有 $n$ 的答案然后 $O(1)$ 查询。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
const int N = 2e6 + 5;
int n, pre[N];
int prime[N], vis[N], cnt;
LL f[N], h[N], ans[N], sum;
vector<PII> rec;
struct Query { int n, id; } Q[N];
// 枚举 x 的约数
void dfs(int x, int div, int idx) {
if (idx == rec.size()) {
sum += h[div];
return;
}
int p = 1;
for (int i = 0; i <= rec[idx].second; i++) {
dfs(x, div * p, idx + 1);
p *= rec[idx].first;
}
}
void work(int x) {
sum += f[x];
int cur = x;
while (pre[cur]) {
cur = pre[cur];
h[cur]++;
sum += (x - 1) / cur;
}
rec.clear();
while (x > 1) { // 质因数分解
if (rec.empty() || vis[x] != rec.back().first) {
rec.push_back({vis[x], 1});
} else {
rec[rec.size() - 1].second++;
}
x /= vis[x];
}
dfs(x, 1, 0);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
n = 2e6;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
vis[i] = i;
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && prime[j] <= n / i; j++) {
vis[prime[j] * i] = prime[j];
if (i % prime[j] == 0) break;
}
}
f[1] = 1;
for (int i = 1; i <= n / 2; i++) {
for (int j = i + i; j <= n; j += i) {
LL now = f[i] + n / i - j / i + 1;
if (now > f[j]) {
f[j] = now;
pre[j] = i;
}
}
}
// for (int i = 1; i <= 100; i++) {
// cout << i << ":" << pre[i] << '\n';
// }
// cout << '\n';
f[1] = 1;
for (int i = 2; i <= n; i++) f[i] = f[pre[i]] - i / pre[i] + 1;
int T;
cin >> T;
for (int i = 1; i <= T; i++) {
cin >> Q[i].n;
Q[i].id = i;
}
sort(Q + 1, Q + 1 + T, [&] (auto a, auto b) { return a.n < b.n; });
int lst = 1;
sum = 1;
for (int i = 1; i <= T; i++) {
if (Q[i].n > lst) {
for (int j = lst + 1; j <= Q[i].n; j++) work(j);
}
ans[Q[i].id] = sum;
lst = Q[i].n;
}
for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
return 0;
}
```