9.4 闲话
XeCtera
·
·
个人记录
Pt. 0
周测又寄了，摆烂不刷题导致的。
怎么还要打高联，唉。
其实早就不会 MO 了，不管了。
今天会了神 wky 提到的这个结论的证明，简单记一下自己的做法。
Pt. 1
设
G(n)=\sum_{i=1}^n\sum_{j=1}^n\dfrac1{ij}[i+j>n][i\perp j]
即需证 G(n)=1 恒成立。
考虑设
F(n)=\sum_{i=1}^n\sum_{j=1}^n\dfrac1{ij}[i+j>n]
然后我们可以在这里枚举 d=\gcd(i,j) 做一个分类。
F(n)=\sum_{d=1}^n\dfrac1{d^2}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\dfrac1{ij}[i+j>n/d][i\perp j]
也就是
F(n)=\sum_{d=1}^n\dfrac1{d^2}G(n/d)
那么假设 G(n)=1 恒成立，应当有 \displaystyle F(n)=\sum_{d=1}^n\dfrac1{d^2}。
容易说明这是充要条件。
上述做法得到的结论本质上是 {\rm d}F={\rm id}^{-2}*{\rm d}G，这里 {\rm d} 表示差分而 * 是狄利克雷卷积。
据此可以直接将问题转化为研究 F 的性质，不再有互质的限制。
其实莫反硬做大概也是可以的。（这里「莫反」指 OI 中常用的 \displaystyle[i\perp j]=\sum_{d|i,d|j}\mu(d) 这个代换技巧）
别常用了，正式比赛一次没用过 /oh
应该会证明出 {\rm d}G=(\mu\cdot{\rm id}^{-2})*{\rm d}F。
再注意到 (\mu\cdot{\rm id}^{-2})*{\rm id}^{-2}=\varepsilon，因此两种方法得出的结论是等价的。
但发现完全没必要引入 \mu 啊！所以前一种做法还是好的。
Pt. 2
现在问题转化为证明
\sum_{i=1}^n\sum_{j=1}^n\dfrac1{ij}[i+j>n]=\sum_{i=1}^n\dfrac1{i^2}
$$\sum_{i=1}^n\sum_{j=1}^n\dfrac1{ij}[i+j\le n]=\left(\sum_{i=1}^n\dfrac1i\right)^2-\sum_{i=1}^n\dfrac1{i^2}$$
此外 $\dfrac{i+j}{ij}=\dfrac1i+\dfrac1j$，这启发我们可以尝试枚举 $k=i+j$。
$$\begin{aligned}LHS&=\sum_{k=1}^n\dfrac1k\sum_{i=1}^{k-1}\dfrac1i+\dfrac1{k-i}\\&=\sum_{k=1}^n\dfrac1k\cdot 2\sum_{i=1}^{k-1}\dfrac1i\\&=2\sum_{1\le i<k\le n}\dfrac1{ik}\\&=\left(\sum_{i=1}^n\dfrac1i\right)^2-\sum_{i=1}^n\dfrac1{i^2}\end{aligned}$$
证毕。
$$\sum_{i=1}^n\sum_{j=1}^n\dfrac1{ij}[i+j>n][i\perp j]=1$$
## Pt. 3
感觉好牛啊！！至少我是只会证明而不可能独立发现这种东西的。
无端联想到另一个恒等式，第一眼看上去同样不知所云：
$$\sum_{i=1}^n\sum_{j=1}^m\min\left(\left\lfloor\dfrac ni\right\rfloor,\left\lfloor\dfrac mj\right\rfloor\right)[i\perp j]=nm$$
但这个的原理要简单得多了。大家也许能一眼秒掉。
不管了，其实早就不会 MO 了。
唉，怎么还要打高联。
摆烂不刷题导致的，周测又寄了。