如何高效地挂分

· · 算法·理论

答：不测样例。

模拟赛最后三十分钟，匆匆写完 T4 的 O(n\log n+m^2) 暴力，大样例却有一个过不了。我定睛一看居然大样例是错的。然后这时候比赛结束了就没管其他两个代码了。结果，除了 T4 一分没得。

事后发现是改了代码忘了改回去。太棒啦，挂了整整 124 分！

这里分享一个 T3 柿子的颓：

\begin{aligned} S(n)&=\frac12\sum_{m=1}^n\sum_{i=1}^m\sum_{j=1}^m[\operatorname{lcm}(\gcd(i,m),\gcd(j,m))\ge m]ij\\ &=\frac12\sum_{m=1}^n\sum_{i|m,i<m}\sum_{j|m,j<m}[\operatorname{lcm}(i,j)=m]\frac{m\varphi(\frac mi)}2\frac{m\varphi(\frac mj)}2\\ &=\frac18\sum_{m=1}^nm^2\sum_{i|m,i<m}\sum_{j|m,j<m}[\operatorname{lcm}(i,j)=m]\varphi\left(\frac mi\right)\varphi\left(\frac mj\right)\\ &=\frac18\sum_{m=1}^nm^2\sum_{i|m,i<m}\sum_{j|m,j<m}\left[\gcd\left(\frac mi,\frac mj\right)=1\right]\varphi\left(\frac mi\right)\varphi\left(\frac mj\right)\\ &=\frac18\sum_{m=1}^nm^2\sum_{i|m,i>1}\sum_{j|m,j>1}[\gcd(i,j)=1]\varphi(i)\varphi(j)\\ &=\frac18\sum_{m=1}^nm^2\sum_{i|m,i>1}\sum_{j|m,j>1}[\gcd(i,j)=1]\varphi(ij)\\ &=\frac18\sum_{m=1}^nm^2\left(\sum_{i|m}\sum_{j|m}[\gcd(i,j)=1]\varphi(ij)-2m+1\right)\\ &=\frac18\sum_{m=1}^n\left(m^2\sum_{i|m}\sum_{j|m}[\gcd(i,j)=1]\varphi(ij)-2m^3+m^2\right)\\ &=\frac18\left(\sum_{m=1}^nm^2\sum_{i|m}\sum_{j|m}[\gcd(i,j)=1]\varphi(ij)-\frac{n^2(n+1)^2}2+\frac{n(n+1)(2n+1)}6\right)\\ &=\frac18\left(\sum_{m=1}^nm^2\sum_{i|m}\sum_{j|m}[\gcd(i,j)=1]\varphi(ij)-\frac{n(n+1)(3n^2+n-1)}6\right)\\ &=\frac18\left(\sum_{m=1}^nm^2\sum_{d|m}\varphi(d)\sum_{ij=d}[\gcd(i,j)=1]-\frac{n(n+1)(3n^2+n-1)}6\right)\\ &=\frac18\left(\sum_{d=1}^n\sum_{m=1}^{\lfloor\frac nd\rfloor}(md)^2\varphi(d)\sum_{ij=d}[\gcd(i,j)=1]-\frac{n(n+1)(3n^2+n-1)}6\right)\\ &=\frac18\left(\sum_{d=1}^n\left(d^2\varphi(d)\sum_{ij=d}[\gcd(i,j)=1]\right)\sum_{m=1}^{\lfloor\frac nd\rfloor}m^2-\frac{n(n+1)(3n^2+n-1)}6\right)\\ &=\frac18\left(\sum_{d=1}^n\left(d^2\varphi(d)\sum_{ij=d}[\gcd(i,j)=1]\right)\frac{\lfloor\frac nd\rfloor(\lfloor\frac nd\rfloor+1)(2\lfloor\frac nd\rfloor+1)}6-\frac{n(n+1)(3n^2+n-1)}6\right)\\ &=\frac1{48}\left(\sum_{d=1}^n\left(d^2\varphi(d)\sum_{ij=d}[\gcd(i,j)=1]\right)\left\lfloor\frac nd\right\rfloor\left(\left\lfloor\frac nd\right\rfloor+1\right)\left(2\left\lfloor\frac nd\right\rfloor+1\right)-n(n+1)(3n^2+n-1)\right)\\ &=\frac1{48}\left(\sum_{d=1}^nd^2\varphi(d)2^{\sigma_p(d)}\left\lfloor\frac nd\right\rfloor\left(\left\lfloor\frac nd\right\rfloor+1\right)\left(2\left\lfloor\frac nd\right\rfloor+1\right)-n(n+1)(3n^2+n-1)\right)\\ \end{aligned}

其中 \sigma_p(d) 表示 d 不同的质因子个数。到此已经可以 Min_25 筛了（d^2\varphi(d)2^{\sigma_p(d)} 是积性函数）。