闲话 8.23
起因是 Rolling_star 在考古 IMO 时发现了这样一道预选题：
给出序列 \(\{a_n\}\) 满足：
\[2^n=\sum_{d|n}{a_d} \]求证：
\[n|a_n \]我们先做一遍底幂交换 （\(Base\) \(power\) \(exchange\)）:
\[2^d=\sum_{n|d}a_n \]然后再指数降阶（$ Exponential$ $reduction $）:
\[\bm{2\times d=\sum_{n|d}{a_n}} \]接着进行直角反演（\(Rotate\) \(the\) \(formula\) \(at\) \(right\) \(angles\) \(before\) \(performing\) \(calculations\)）
\[2\times d=\frac{\omega d}{n}\times a_n \]显然消去 \(d\) ：
\[\frac{2}{\omega}=\frac{a_n}{n} \]显然 \(\omega\) 是角速度，这是我们上文在使用直角反演时所产生的，是 \(O(\omega)\) 级别的，所以有
\[\displaystyle\frac{2}{\omega}=\frac{2}{\Theta(\log n)}=\frac{2/\log n}{O()}=\frac{2/\log n}{(O)}=\frac{4}{(O_2)\log n}=4O_{2\log n}\uparrow \]这样，我们就得到了 \(4\text{ mol}\) 的 \(O_{2\log n}\)，
\[\begin{aligned}&O_{2\log n}\xlongequal[\text{催化剂}]{\Delta}\log n\cdot O_2\\&O_{2\log n}\xlongequal[\mathrm{B_2 O_2},\mathrm{B_{20}},\mathrm{K_8He}]{\Theta(2^{n/2})\ {}^{\circ}\text{C}}2\cdot O_{\log n}\end{aligned} \]联立可以得到 \(2/\log n=O_2/O_{\log n}\)，两边取对数：
\[\begin{aligned}&\log 2-\log\log n=2\log O-n\log O\\\implies&\log 2-\log\omega=(2-n)\log O\end{aligned} \]在 word-RAM model 下可以认为 \(\omega=\Theta(1)\)，那么可以得到
\[(2-n)\log O=O(1)=O(n) \]消去括号及 \(O\)，就可以得到 \(2-n\log=n\)，移项即得 \(2^{2/n}=2\cdot2^{\log}=2\)，解得 \(n=2\)，代回 \(\omega\) 的渐进式：
\[\omega=O(\log n)=O(1) \]可得：
\[n|a_n \]\[\mathcal{Q.E.D} \] 标签：frac,log,闲话,sum,text,8.23,aligned,omega From： https://www.cnblogs.com/shen666zxcmt/p/17652723.html