「闲话随笔」恋恋扰动星之器
点击查看目录
目录
其实就是写一个 koishi 的数学题的题解和星之器的题解和扰动法的讲解。
jijidawang 说今天是恋恋日所以推荐我写 koishi 的数学题，不然这篇闲话是没有这道题的。
为啥我盯了高二人半天好像只有 Delov 看了我一眼啊。
吃完晚饭回机房刚好赶上高一下课，被堵了，差点和人撞到融合。
推歌：粉色柠檬。
推这首歌和这首歌好不好听没关系，只是对于歌手与发行年份比较有感触。（但不是说这首歌不好听。）
寒假的时候出了乐正绫 AI，于是也出现了一些这首歌的星尘 Infinity + 洛天依 AI + 乐正绫 AI 的翻调，进一步加深了感触。
比较怀念那段日子。
koishi 的数学题
推式子：
\[\begin{aligned} f(x) &= \sum_{i = 1}^{n} x \bmod{i}\\ &= \sum_{i = 1}^{n} x - i\left\lfloor\frac{x}{i}\right\rfloor\\ &= nx - \sum_{i = 1}^{n}i\left\lfloor\frac{x}{i}\right\rfloor\\ \end{aligned} \]\(nx\) 不用管，考虑快速算出 \(\sum_{i = 1}^{n}i\left\lfloor\frac{x}{i}\right\rfloor\)。直接算没法算，那就考虑从 \(f(x)\) 递推到 \(f(x + 1)\)。
不难发现当且仅当 \(i\) 为 \(x + 1\) 因数时，\(\left\lfloor\frac{x}{i}\right\rfloor\) 会增加一，因此 \(x + 1\) 对 \(\sum_{i = 1}^{n}i\left\lfloor\frac{x}{i}\right\rfloor\) 的贡献为其因数之和。
线性筛来一发。
星之器
属实神仙题。
不难发现行和列对于答案的贡献是单独计算的。
设 \(\phi(x)\) 是对于某一维中坐标为 \(x\) 的星的势能，势能的变化量为对答案的贡献。这个 \(\phi(x)\) 不好求出，但可以用它的变化量表示出来这个式子：
\[\phi(x) - \phi(x + 1) + \phi(y) - \phi(y - 1) = y - x - 1 (x < y) \]稍微移个项：
\[\phi(x + 1) - \phi(x) - (x + 1) = \phi(y) - \phi(y - 1) - y \]不难发现 \(\phi(x + 1) - \phi(x) - (x + 1)\) 是个定值，那么构造出一个 \(\phi(x)\) 满足这个式子是个定值就行了。
题解里构造的大都是 \(\phi(x) = \frac{x(x + 1)}{2}\)，jijidawang 构造了一个 \(\phi(x) = \frac{x^2}{2} + x\)，我构造了一组也是 \(\phi(x) = \frac{x(x + 1)}{2}\)。
然后每颗星 \((x,y)\) 的势能就是 \(\frac{x(x + 1) + y(y + 1)}{2}\)，由于「势能的变化量为对答案的贡献」，答案就是初始状态下的总势能减去最终状态的总势能。
挺有意思。
扰动法
大概就是化简一个和式的过程中，通过提出等式左边的末项和等式右边的首项，通过一顿操作化简掉的方法。
例如等比数列求和：\(Sn = \sum_{i = 0}^{n}A^{i}\)
\[\begin{aligned} Sn + A^{n + 1} &= 1 + \sum_{i = 1}^{n + 1}A^{i}\\ Sn + A^{n + 1} &= 1 + ASn\\ (A - 1)Sn &= A^{n + 1} - 1\\ Sn &= \frac{A^{n + 1} - 1}{A - 1}\\ \end{aligned} \]一个简单例子：化简 \(\sum_{k = 1}^{n}k2^{k}\)。
这个是某天 xrlong 问我的，我用扰动法推出来后一翻混凝土数学发现是原
标签：phi,aligned,frac,恋恋,星之器,sum,Sn,随笔 From： https://www.cnblogs.com/Keven-He/p/chat_20230514.html