P1829 [国家集训队] Crash的数字表格 / JZPTAB
不妨假设 \(n < m\)。
\[\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^m\dfrac{ij}{\gcd(i, j)} &= \sum_{d = 1}^n\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i, j) = d]\dfrac{ij}{d}\\ \\ &= \sum_{d = 1}^n\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i, j) = 1]ijd\\ \\ &= \sum_{d = 1}^n\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j = 1}^{\lfloor\frac{m}{d}\rfloor}ijd\sum_{k \mid \gcd(i, j)}\mu(k)\\ \\ &= \sum_{d = 1}^n\sum_{k = 1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\cdot k^2\sum_{i = 1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j = 1}^{\lfloor\frac{m}{dk}\rfloor}jd\\ \end{aligned} \]定义 \(f(n) = \sum_{i = 1}^ni\)。
枚举 \(T = dk\)。
\[\begin{aligned} &= \sum_{d = 1}^n\sum_{k = 1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\cdot k^2f(\lfloor\frac{n}{dk}\rfloor)\cdot f(\lfloor\frac{m}{dk}\rfloor)\cdot d\\ \\ &= \sum_{T = 1}^{n}f(\lfloor\dfrac{n}{T}\rfloor)\cdot f(\lfloor\dfrac{m}{T}\rfloor)\cdot \sum_{d \mid T}\mu(\dfrac{T}{d})\cdot (\dfrac{T}{d})^2 \cdot d\\ \\ &= \sum_{T = 1}^{n}f(\lfloor\dfrac{n}{T}\rfloor)\cdot f(\lfloor\dfrac{m}{T}\rfloor)\cdot \sum_{d \mid T}\mu(d)\cdot d \cdot T\\ \end{aligned} \]数论函数的积性在卷积中封闭。
由于 \(g(T) = \mu(T) \cdot T\) 是积性函数（\(id\) 完全积性，显然成立），那么 \(F(T) = \sum_{d \mid T}\mu(d)\cdot d = g * 1\) 也是积性函数。
即求
\[\sum_{T = 1}^{n}f(\lfloor\dfrac{n}{T}\rfloor)\cdot f(\lfloor\dfrac{m}{T}\rfloor)\cdot T\cdot F(T)\\ \]可以线性筛预处理 \(T \cdot F(T)\) 的前缀和，然后数论分块。（对于函数 \(F\)，任意质数的幂次 \(F(p^k) = 1 - p\)）
P3327 [SDOI2015] 约数个数和
有结论
\[d(ij) = \sum_{x \mid i}\sum_{y\mid j}[\gcd(x, y) = 1] \]假定 \(i = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \ j = p_1^{b_1}p_2^{b_2}\cdots p_k^{b_k}\)。
任意一个素数因子对答案贡献的形式是相同的，单独考虑一个 \(p_c\)，则答案一定可以写成 \(f(p_c) \cdot X\)。
左边：\(f(p_c) = a_c + b_c + 1\)。
右边：用一个数对表示 \(p_c\) 在 \(x\) 和 \(y\) 中出现的幂次，形如 \((\alpha, 0)\) 或 \((0, \beta)\) 的合法，则合法数对数即 \(f(p_c) = a_c + b_c + 1\)。
左边等于右边。
利用上述公式推导：
\[\begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^md(ij) &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{x \mid i}\sum_{y\mid j}[\gcd(x, y) = 1]\\ \\ &= \sum_{x = 1}^n\sum_{y = 1}^m\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor \cdot [\gcd(x, y) = 1]\\ \\ &= \sum_{x = 1}^n\sum_{y = 1}^m\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor \cdot \sum_{k \mid \gcd(x, y)}\mu(k)\\ \\ &= \sum_{k = 1}^n\mu(k)\sum_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\dfrac{n}{ik}\rfloor\cdot \sum_{j = 1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\dfrac{m}{jk}\rfloor\\ \end{aligned} \]记 \(f(n) = \sum_{i = 1}^n\lfloor\dfrac{n}{i}\rfloor\)。
由于
\[\lfloor\dfrac{n}{ik}\rfloor = \lfloor\dfrac{\lfloor\dfrac{n}{k}\rfloor}{i}\rfloor \]即求
\[\sum_{k = 1}^n\mu(k)\cdot f(\lfloor\frac{n}{k}\rfloor)\cdot f(\lfloor\frac{m}{k}\rfloor) \]后面两项可以 \(O(N\sqrt N)\) 预处理，也可以加个记忆化在线算。
标签：lfloor,frac,莫反小练,cdot,dfrac,sum,rfloor From： https://www.cnblogs.com/Luxinze/p/18198747