关于今天T4复杂度证明的人话翻译：（我是只会搞T4了吗）
首先我们略去前面的所有东西，直接到证明这个贪心处理之后的向量个数在 \(O(n^{\frac 23})\) 级别：
考察我们之前选择向量的过程，我们选择一个向量 \((i,j)\) 之前，先要选择所有 \(x,y\) 严格小于它的所有向量，同时要求这些向量的 \(x,y\) 加和不超过 \(2n\) 。然后得到一个显然的式子：
\[\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\left[\sum_{x=1}^i\sum_{y=1}^j[\gcd(x,y)=1](x+y)\le 2n\right] \]然后逐渐翻译一下：首先右边那个艾弗森括号左右都除以个 \(2\) ：
\[\le\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\left[\max\left(\sum_{x=1}^i\sum_{y=1}^j[\gcd(x,y)=1]x,\sum_{x=1}^i\sum_{y=1}^j[\gcd(x,y)=1]y\right)\le n\right] \]使用显然的莫比乌斯反演：（不展开）
\[=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\left[\max\left(\sum_{d=1}^{\infty}\mu(d)d\sum_{x=1}^{\lfloor\frac id\rfloor}\sum_{y=1}^{\lfloor\frac jd\rfloor}x,\sum_{d=1}^{\infty}\mu(d)d\sum_{x=1}^{\lfloor\frac id\rfloor}\sum_{y=1}^{\lfloor\frac jd\rfloor}y\right)\le n\right] \]关于 \(d\) 的上界问题，发现实际上取 \(\max(x,y)\) 还是 \(\infty\) 没有实质上的区别，但是 \(\infty\) 更好讨论一些。
然后把左边的艾弗森括号去掉，变成 \(\le\) ：
\[\le\sum_{i=1}^n\sum_{j=1}^n\left[\max\left(\sum_{d=1}^{\infty}\mu(d)d\sum_{x=1}^{\lfloor\frac id\rfloor}\sum_{y=1}^{\lfloor\frac jd\rfloor}x,\sum_{d=1}^{\infty}\mu(d)d\sum_{x=1}^{\lfloor\frac id\rfloor}\sum_{y=1}^{\lfloor\frac jd\rfloor}y\right)\le n\right] \]现在我们考察和式内部的式子
\[\sum_{x=1}^{\lfloor\frac id\rfloor}\sum_{y=1}^{\lfloor\frac jd\rfloor}x \]它的值显然是（把向下取整删掉了，并不影响）
\[\begin{aligned} &\frac jd\frac{(1+\frac id)\frac id}2\\ =&\frac{i^2j}{d^3}\\ \end{aligned} \]这里由于是复杂度证明，我们省略了常数。然后类似的，右边就是 \(\frac{ij^2}{d^3}\) 。左右取最大值，就是
\[\frac {ij\max(i,j)}{d^3} \]代入原来的式子：
\[\begin{aligned} &\sum_{d=1}^{\infty}\mu(d)d\frac {ij\max(i,j)}{d^3}\\ =&ij\max(i,j)\sum_{d=1}^{\infty}\frac {\mu(d)}{d^2} \end{aligned} \]现在开始讨论右边的和式。我们将所有的 \(\mu(d)\) 近似成 \(1\) ，可以得到：
\[\sum_{d=1}^{\infty}\frac {\mu(d)}{d^2}\le\sum_{d=1}^{\infty}\frac 1{d^2} \]右边的东西我们知道是 \(\frac {\pi^2}6\) 。所以代回原式，有：
\[\sum_{i=1}^n\sum_{j=1}^n[ij\max(i,j)\le \Theta(n)] \]显然有贡献的 \(i,j\) 的级别是 \(O(n^{\frac 13})\) 级别的。所以上界就是 \(O(n^{\frac 23})\) 。证毕。
标签：lfloor,infty,le,frac,sum,rfloor,证明,复杂度,T4 From： https://www.cnblogs.com/gtm1514/p/16749248.html