P6156 简单题 题解
题目大意
给定 \(n,k\)，求 \(\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\)。
\(1\leq n\leq5\times10^6\)
题目分析
先推导一波式子：
\[\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\gcd(i,j)\mu^2(\gcd(i,j))\\ &=\sum_{t=1}^nt^{k+1}\mu^2(t)\sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=t]\\ &=\sum_{t=1}^nt^{k+1}\mu^2(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{t}\rfloor}(i+j)^k\sum_{d|i,d|j}\mu(d)\\ &=\sum_{t=1}^nt^{k+1}\mu^2(t)\sum_{d=1}^{\lfloor\frac{n}{t}\rfloor}d^k\mu(d)\sum_{i=1}^{\lfloor\frac{n}{td}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{td}\rfloor}(i+j)^k\\ \end{aligned} \]令 \(S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\)，
\[ans=\sum_{t=1}^n\sum_{d=1}^nt^{k+1}d^k\mu^2(t)\mu(d)S(\lfloor\frac{n}{td}\rfloor) \]设 \(T=td\)，
\[ans=\sum_{T=1}^nT^kS(\lfloor\frac{n}{T}\rfloor)\sum_{d|T}d\mu^2(d)\mu(\frac{T}d) \]-
先考虑快速求出 \(S(n)\)
令 \(F(n)=\sum_{i=1}^ni^k,G(n)=\sum_{i=1}^nF(i)\)。
则有 \(S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i)=G(2n)-2G(n)\)。
而 \(F(n)\) 可以用欧拉筛筛出来。
-
在考虑 \(f(n)=\sum_{d|n}d\mu^2(d)\mu(\frac{T}d)\)
显然 \(f(n)\) 也是积性函数。
从 \(\mu\) 函数考虑，讨论 \(p\) 在 \(n\) 中的最高次幂，既有 \(p^k|x\and p^{k+1}\not\mid x\)。
因为有 \(f(n)=f(p^k)\times f(\frac{n}{p^k})\)，所以讨论 \(f(p^k)\) 的取值：
- \(k=0\)，则 \(f(1)=1\)。
- \(k=1\)，则 \(f(p)=1\mu^2(1)\mu(p)+p\mu^2(p)\mu(1)=p-1\)。
- \(k=2\)，则 \(f(p^2)=1\mu^2(1)\mu(p^2)+p\mu^2(p)\mu(p)+p^2\mu^2(p^2)\mu(1)=-p\)。
- \(k\geq3\)，根据鸽巢定理，此时 \(\mu(d)=0\or \mu(\frac{n}d)=0\)，则 \(f(p^k)=0\)。
于是可以计算出 \(f(n)\)。