交换求和号
交换求和号是 OI 中常用的数学技巧……
考虑（这里 \(\bigcup B(i)\) 表示把所有 \(B(i)\) 拼接起来的集合，而不是集合的并）
\[\sum_{i\in A}\sum_{j\in\bigcup_{i\in A} B(i)}f(i,j) \]我们期望得到交换求和号后的形式（在 OI 中，我们大概并不会遇到无限求和的情形），即
\[\sum_{j\in C}\sum_{i\in\bigcup_{j\in C} D(j)}f(i,j)=\sum_{i\in A}\sum_{j\in\bigcup_{i\in A} B(i)}f(i,j) \]显然，我们有 \(C=\bigcup\limits_{i\in A} B(i)\)。
现在的问题是求出函数 \(D\)。
考虑 \(B(i)\) 的反向映射 \(B^\prime(x)\) 表示
\[B^\prime(x)=\{i\mid x\in B(i)\} \]显然就有
\[\bigcup_{j\in C} D(j)=\left(\bigcup_{x\in C}B^\prime(x)\right)\cap A \]交换求和号的好处是显而易见的，因为我们有
\[\sum_{i\in A}\sum_{j\in\bigcup B(i)}f(i,j)g(i)=\sum_{i\in A}g(i)\sum_{j\in\bigcup B(i)}f(i,j) \]如果 \(\sum f(i,j)\) 是个容易处理的函数，那么就可以得到大为简化的结果。
比如下面这个例子
\[\begin{align*} \sum_{d=1}^n\varphi(d)\lfloor\frac{n}{d}\rfloor&=\sum_{d=1}^n\varphi(d)\sum_{i=1\\d|i}^n1\\ &=\sum_{d=1}^n\sum_{i=1\\d|i}^n\varphi(d)\\ &=\sum_{i=1}^n\sum_{d|i}\varphi(d)\\ &=\sum_{i=1}^ni\\ &=\frac{n(n+1)}{2} \end{align*} \]第二行到第三行的变换中，我们交换了 \(i,d\) 的求和顺序，更为具体的，我们可以写出
\[\sum_{d\in[1,n]\cap \mathbb{N}}\sum_{i=kd,\\k\in[1,\frac{n}{d}]\cap\mathbb{N}}\varphi(d)=\sum_{i\in [1,n]\cap\mathbb{N}}\sum_{d\mid i}\varphi(d) \]可以显然的看出 \(A=C=[1,n]\cap\mathbb{N}\)，而 \(B(i)\) 从 \(i\) 映射到 \(i\) 在 \(A\) 中的倍数，那么 \(B^\prime(i)\) 就应当映射了 \(i\) 的约数。
用莫比乌斯变换做一个更加困难的例子：
假如已知 \(f(n)=\sum\limits_{d\mid n}g(d)\)。
那么
\[\begin{align*} \sum_{d\mid n}\mu(d)f(\frac{n}{d})&=\sum_{d\mid n}\mu(d)\sum_{d^\prime\mid\frac{n}{d}}g(d^\prime)\\ &=\sum_{d\mid n}\sum_{d^\prime\mid\frac{n}{d}}\mu(d)g(d^\prime)\\ &=\sum_{dd^\prime\mid n}\mu(d)g(d^\prime)\\ &=\sum_{d^\prime\mid n}\sum_{d\mid\frac{n}{d^\prime}}\mu(d)g(d^\prime)\\ &=\sum_{d^\prime\mid n}g(d^\prime)\sum_{d\mid\frac{n}{d^\prime}}\mu(d)\\ &=\sum_{d^\prime\mid n}g(d^\prime)[\frac{n}{d^\prime}=1]\\ &=g(n) \end{align*} \]在 \(2\sim4\) 行的推导中，我们先把 \(\sum\limits_{d\mid n}\sum\limits_{d^\prime\mid\frac{n}{d}}\) 变为了 \(\sum\limits_{dd^\prime\mid n}\)，然后再重新展开，就实现了交换求和号。
这启发我们
\[\sum_{i\in A}\sum_{j\in B(i\mid i\in A)}f(i,j)=\sum_{(i,j)\in A\times B(i\mid i\in A)}f(i,j) \]交换求和号的实质就是
\[A\times B(i\mid i\in A)=D(j\mid j\in C)\times C \]然后其实我们没有用到 \(+\) 的性质，所以把上面的 \(\sum\) 换成 \(\prod\) 之类的也是成立的。（需要满足分配率和结合律，推导不依赖 \(f\) 的性质）
标签：prime,frac,求和,sum,交换,mid,bigcup From： https://www.cnblogs.com/efX-bk/p/swap_the_Sum.html