SP33039题解 - AFS3

· · 题解

这 sk 写的是什么玩意，给个阳间代码和完整式子。

以下的除法皆是下取整。

众所周知，\sigma=\text{Id}*1，于是有

\text{ans}+n(n-1)/2=\sum_{i=1}^n\sum_{d|i}d=\sum_{d=1}^nd(n/d)

也就相当于：每个整点都有相当于其横坐标的权值，要统计 y=n/x(x>0)、横轴正半轴和纵轴正半轴围成的图像中所有整点的权值和。

再转化一下是（其中 B=\lfloor \sqrt n\rfloor）

\color{red}\sum_{d=1}^Bd(n/d)\color{black}+\color{blue}\sum_{d=1}^{B}(n/d)\cdot(n/d+1)/2\color{black}-B^2(B+1)/2

红色部分其实统计的是这个图形的左半部分，下面我们把它折到下半来，这样就可以和红色一起计算了。

对于向量 (x,y)，我们记

T_{k_1,k_2}(x,y)=\sum_{i=0}^{y-1}i^{k_1}\lfloor xi/y\rfloor^{k_2}

其实就是从 (0,0) 开始移到 (x,y) 的答案。

考虑从 (x_p,y_p) 开始移到 (x_p+x_L,y_p-x_L)，获得的答案为

\begin{aligned} &-x_p-y_p+\sum_{i=0}^{y_L-1}(y_p-i)(x_p+\lfloor x_Li/y_L\rfloor)+(x_p+\lfloor x_Li/y_L\rfloor)(x_p+\lfloor x_Li/y_L\rfloor+1)/2\\ =&\texttt{暴力展开} \end{aligned}

最后考虑合并两个向量，由于这两个向量在 SBT 上是相邻的，所以首尾相接的答案其实就是合并后的答案：

T_{0,1}(M)=T_{0,1}(L)+x_Ly_R+T_{0,1}(R) T_{1,1}(M)=T_{1,1}(L)+\sum_{i=0}^{y_R-1}(i+y_L)(x_L+\lfloor x_Ri/y_R\rfloor)=\texttt{暴力展开} T_{0,2}(M)=T_{0,2}(L)+\sum_{i=0}^{y_R-1}(x_L+\lfloor x_Ri/y_R\rfloor)^2=\texttt{暴力展开}

具体式子可以见代码。不推荐直接贺，否则下次你想写的时候绝对无法在合理的时间内调出来……

#include<bits/stdc++.h>
typedef long long ll;
typedef __int128 lll;
using namespace std;

void outp(lll x) {
    if (!x) return;
    outp(x / 10); printf("%d", (int)(x % 10));
}
struct vec {
    ll x, y;
    vec () : x(0), y(0){}
    vec (ll x0, ll y0) : x(x0), y(y0){}
    vec operator + (const vec b) const { return {x + b.x, y + b.y}; }
};
struct vecer {
    vec p;
    lll v[3]; //(0, 1), (1, 1), (0, 2)
};

ll n;
vector<vecer> stk;
vec p;

bool ninR(const vec &a) { return n < (lll)a.x * a.y; }
bool steep(const ll &x, const vec &a) { return (lll)n * a.x <= (lll)x * x * a.y; }

lll calc(ll b) {
    return (lll)(b + 1) * b / 2;
}

int cnt = 0;

lll solve() {
    ll sqr = sqrt(n), cbr = cbrt(n);
    p = {n / sqr + 1, sqr};
    lll ans = 0;
    stk.push_back({{1, 0}, 0, 0, 0});
    stk.push_back({{1, 1}, 0, 0, 0});
    while (1) {
        if (stk.empty()) printf("ERROR!\n");
        vecer L = stk.back(); stk.pop_back();
        while (ninR({p.x + L.p.x, p.y - L.p.y})) {
            ans += (lll)p.x * p.y * L.p.y + (lll)p.y * L.v[0] - (lll)p.x * calc(L.p.y - 1) - L.v[1];
            ans += (lll)calc(p.x) * L.p.y + ((lll)(2 * p.x + 1) * L.v[0] + L.v[2]) / 2;
            ans -= p.x + p.y;
            p.x += L.p.x; p.y -= L.p.y;
        }
        if (p.y <= cbr) break;
        vecer R = stk.back();
        while (!ninR({p.x + R.p.x, p.y - R.p.y}))
            L = R, stk.pop_back(), R = stk.back();
        while (1) {
            vecer mid;
            mid.p = L.p + R.p;
            mid.v[0] = L.v[0] + (lll)L.p.x * R.p.y + R.v[0];
            mid.v[1] = L.v[1] + (lll)L.p.x * calc(R.p.y - 1) + (lll)L.p.x * L.p.y * R.p.y + R.v[1] + (lll)L.p.y * R.v[0];
            mid.v[2] = L.v[2] + (lll)L.p.x * L.p.x * R.p.y + (lll)2 * L.p.x * R.v[0] + R.v[2];
            if (ninR({p.x + mid.p.x, p.y - mid.p.y})) stk.push_back(R = mid);
            else if (steep(p.x + mid.p.x, R.p)) break;
            else L = mid;
        }
    }
    for (int i = 1; i <= p.y; i++)
        ans += (lll)n / i * i + (lll)(n / i + 1) * (n / i) / 2;
    return ans - (lll)sqr * sqr * (sqr + 1) / 2 - (lll)n * (n + 1) / 2;
    stk.clear();
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n); 
        lll ans = solve();
        if (ans == 0) printf("0\n");
        outp(ans); printf("\n");
    }
}