莫比乌斯反演总结

\[\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\operatorname{lcm}(i, j)\\ = \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\sum\limits_{k |i, j}[\gcd(i, j) = k] \times \frac{ij}{k}\\ = \sum\limits_{k}^{\min(n, m)}k\times\sum\limits_{i = 1}^{\frac{n}{k}}i\sum\limits_{j = 1}^{\frac{m}{k}}j\times[gcd(i, j) = 1]\\ = \sum\limits_{k}^{\min(n, m)}k\times\sum\limits_{i = 1}^{\frac{n}{k}}i\sum\limits_{j = 1}^{\frac{m}{k}}j\sum\limits_{e | i, j}\mu(e)\\ = \sum\limits_{k}^{\min(n, m)}k\times\sum\limits_{e}^{\min(\frac{n}{k}, \frac{m}{k})}\mu(e)\times\sum\limits_{i = 1}^{\frac{n}{ke}}\sum\limits_{j = 1}^{\frac{m}{ke}}ij\\ = \sum\limits_{k}^{\min(n, m)}k\times\sum\limits_{e}^{\min(\frac{n}{k}, \frac{m}{k})}\mu(e)\frac{(1 + \lfloor\frac{n}{ke}\rfloor) \times \lfloor\frac{n}{ke}\rfloor}{2}\frac{(1 + \lfloor\frac{m}{ke}\rfloor) \times \lfloor\frac{m}{ke}\rfloor}{2}\\ \]

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)\\ = \sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x, y) = 1]\\ = \sum\limits_{x}^{n}\sum\limits_{y}^{m}[\gcd(x, y) = 1]\sum\limits_{i}^{\frac{n}{x}}\sum\limits_{j}^{\frac{m}{y}}1\\ = \sum\limits_{x}^{n}\sum\limits_{y}^{m}[\gcd(x, y) = 1]\lfloor\frac{n}{x}\rfloor\lfloor\frac{n}{y}\rfloor\\ = \sum\limits_{x}^{n}\sum\limits_{y}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{n}{y}\rfloor[\gcd(x, y) = 1]\\ = \sum\limits_{x}^{n}\sum\limits_{y}^{m}\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\sum_{i|x, y}\mu(i)\\ = \sum_{i}^{\min(n, m)}\mu(i)\sum\limits_{x}^{\frac{n}{i}}\sum\limits_{y}^{\frac{m}{i}}\lfloor\frac{n}{xi}\rfloor\lfloor\frac{m}{yi}\rfloor\\ = \sum_{i}^{\min(n, m)}\mu(i)\sum\limits_{x}^{\frac{n}{i}}\lfloor\frac{n}{xi}\rfloor\sum\limits_{y}^{\frac{m}{i}}\lfloor\frac{m}{yi}\rfloor\\ = \sum_{i}^{\min(n, m)}\mu(i)(\sum\limits_{x}^{\frac{n}{i}}\lfloor\frac{n}{xi}\rfloor)(\sum\limits_{y}^{\frac{m}{i}}\lfloor\frac{m}{yi}\rfloor)\\ \]

\[\sum\limits_{i = 1}^{a}\sum\limits_{j = 1}^{b}[\gcd(i, j) = d]\\ = \sum\limits_{i = 1}^{\frac{a}{d}}\sum\limits_{j = 1}^{\frac{b}{d}}[\gcd(i, j) = 1]\\ = \sum\limits_{i = 1}^{\frac{a}{d}}\sum\limits_{j = 1}^{\frac{b}{d}}\sum\limits_{e | i, j}\mu(e)\\ = \sum\limits_{e = 1}^{\min(\frac{a}{d}, \frac{b}{d})}\mu(e)\sum\limits_{i = 1}^{\frac{a}{ed}}\sum\limits_{j = 1}^{\frac{b}{ed}}1\\ = \sum\limits_{e = 1}^{\min(\frac{a}{d}, \frac{b}{d})}\mu(e)\lfloor\frac{a}{ed}\rfloor\lfloor\frac{b}{ed}\rfloor\\ \]

\[(2 \times\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\gcd(i, j)) - nm \]

\[\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\gcd(i, j)\\ = \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}\sum\limits_{k = 1}^{\min(n, m)}k[\gcd(i, j) = k]\\ = \sum\limits_{k = 1}^{\min(n, m)}k \times\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}[\gcd(i, j) = k]\\ = \sum\limits_{k = 1}^{\min(n, m)}k \times\sum\limits_{i = 1}^{\frac{n}{k}}\sum\limits_{j = 1}^{\frac{m}{k}}[\gcd(i, j) = 1]\\ = \sum\limits_{k = 1}^{\min(n, m)}k \times\sum\limits_{i = 1}^{\frac{n}{k}}\sum\limits_{j = 1}^{\frac{m}{k}}\sum\limits_{e | i, j} \mu(e)\\ = \sum\limits_{k = 1}^{\min(n, m)}k\times\sum\limits_{e = 1}^{\frac{\min(n, m)}{k}}\mu(e)\sum\limits_{i = 1}^{\frac{n}{ke}}\sum\limits_{j = 1}^{\frac{m}{ke}}1\\ = \sum\limits_{k = 1}^{\min(n, m)}k\times\sum\limits_{e = 1}^{\frac{\min(n, m)}{k}}\mu(e)\lfloor\frac{n}{ke}\rfloor\lfloor\frac{m}{ke}\rfloor\\ \]

\[\sum\limits_{i=0}^{n-2}\ \sum\limits_{j=i+1}^{n-1}\ \mathrm{lcm}(A_i,A_j)\\ = \frac{(\sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{m}\mathrm{lcm}(i, j)\times\mathrm{number}(i)\times\mathrm{number}(j)) - \sum\limits_{i = 0}^{n - 1}A_i}{2} \]

\[\sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{m}\mathrm{lcm}(i, j)\times\mathrm{number}(i)\times\mathrm{number}(j)\\ =\sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{m}\mathrm{number}(i)\times\mathrm{number}(j)\times\frac{ij}{\gcd(i, j)}\\ =\sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{m}\mathrm{number}(i)\times\mathrm{number}(j)\times\sum\limits_{k}^{m}\frac{ij}{k}[\gcd(i, j) = k]\\ =\sum\limits_{k}^{m}\sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{m}\mathrm{number}(i)\times\mathrm{number}(j)\times\frac{ij}{k}[\gcd(i, j) = k]\\ =\sum\limits_{k}^{m}k\times\sum\limits_{i = 1}^{\frac{m}{k}}\sum\limits_{j = 1}^{\frac{m}{k}}\mathrm{number}(ik)\times\mathrm{number}(jk)\times ij[\gcd(i, j) = 1]\\ =\sum\limits_{k}^{m}k\times\sum\limits_{i = 1}^{\frac{m}{k}}\sum\limits_{j = 1}^{\frac{m}{k}}\mathrm{number}(ik)\times\mathrm{number}(jk)\times ij\sum\limits_{e | i, j}\mu(e)\\ =\sum\limits_{k}^{m}k\times\sum\limits_{e}^{\frac{m}{k}}\mu(e) \times e^{2}\sum\limits_{i = 1}^{\frac{m}{ke}}\sum\limits_{j = 1}^{\frac{m}{ke}}\mathrm{number}(ike)\times\mathrm{number}(jke)\times ij\\ =\sum\limits_{e}^{m}\mu(e) \times e^{2}\sum\limits_{k}^{\frac{m}{e}}k\times\sum\limits_{i = 1}^{\frac{m}{ke}}\sum\limits_{j = 1}^{\frac{m}{ke}}\mathrm{number}(ike)\times\mathrm{number}(jke)\times ij\\ =\sum\limits_{e}^{m}\mu(e) \times e^{2}\sum\limits_{k}^{\frac{m}{e}}k\times\sum\limits_{i = 1}^{\frac{m}{ke}}\mathrm{number}(ike)\times i\sum\limits_{j = 1}^{\frac{m}{ke}}\mathrm{number}(jke)\times j\\ =\sum\limits_{e}^{m}\mu(e) \times e^{2}\sum\limits_{k}^{\frac{m}{e}}k\times(\sum\limits_{i = 1}^{\frac{m}{ke}}\mathrm{number}(ike)\times i)^{2}\\ \]