警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「洛谷 P3768」简单的数学题 - 莫比乌斯反演 + 杜教筛

题意

传送门:洛谷 P3768 - 简单的数学题

\(n,p\),求 \(\sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot\gcd(i,j)\)

\(1\le n\le10^{10},5\times10^8\le p\le1.1\times10^9,p~\text{is prime}\)

解法

\(\operatorname{sumx}(y)=\sum_{i=1}^yi^x\)

\[ \begin{aligned} & \begin{aligned} & \sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot\gcd(i,j) \\ = & \sum_{k=1}^nk^3\sum_{i=1}^{\left\lfloor\frac nk\right\rfloor}\sum_{j=1}^{\left\lfloor\frac nk\right\rfloor}\sum_{d\mid\gcd(i,j)}\mu(d)i\cdot j \\ = & \sum_{k=1}^nk^3\sum_{d=1}^{\left\lfloor\frac nk\right\rfloor}\mu(d)d^2\operatorname{sum}\left(\left\lfloor\frac n{dk}\right\rfloor\right)^2 \\ = & \sum_{T=1}^n\operatorname{sum3}\left(\left\lfloor\frac nT\right\rfloor\right)\sum_{k\mid T}\left(\frac Tk\right)^2\mu\left(\frac Tk\right)k^3 \\ = & \sum_{T=1}^n\operatorname{sum3}\left(\left\lfloor\frac nT\right\rfloor\right)\sum_{k\mid T}T^2k\mu\left(\frac Tk\right) \\ = & \sum_{T=1}^n\operatorname{sum3}\left(\left\lfloor\frac nT\right\rfloor\right)T^2\sum_{k\mid T}k\mu\left(\frac Tk\right) \\ = & \sum_{T=1}^n\operatorname{sum3}\left(\left\lfloor\frac nT\right\rfloor\right)T^2\varphi(T) \\ \end{aligned} \\ & \text{let}~f(n) = n^2\varphi(n),\quad S(n) = \sum_{i=1}^nf(i),\quad g(n)=n^2 \\ & \begin{aligned} & (f*g)(n) \\ = & \sum_{d|n}f(d)g\left(\frac nd\right) \\ = & \sum_{d|n}d^2\varphi(d)\frac{n^2}{d^2} \\ = & n^2\sum_{d|n}\varphi(d) \\ = & n^3 \\ & g(1)S(n) = S(n) \\ = & \sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac nd\right\rfloor\right) \\ = & \sum_{i=1}^ni^3-\sum_{i=2}^ni^2S\left(\left\lfloor\frac nd\right\rfloor\right) \\ = & \operatorname{sum3}(n)-\sum_{i=2}^ni^2S\left(\left\lfloor\frac nd\right\rfloor\right) \\ \end{aligned} \end{aligned} \]

然后杜教筛,就完了。

代码