警告

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

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

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

点击屏幕以关闭。

「SDOI 2017」数字表格 - 莫比乌斯反演

题意

传送门:洛谷 P3704 - 数字表格

\(\sum_{i=1}^n\sum_{j=1}^mF_{\gcd(i,j)}\),其中 \(F\) 为斐波那契数列。

\(n, m \le 10^7\)

解法

推柿子。

\[ \begin{aligned} & \text{suppose}~n\le m,\\ & \begin{aligned} & \prod_{i=1}^n\prod_{j=1}^mF_{\gcd(i,j)} \\ = & \prod_{k=1}^nF_k^{\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]} \\ = & \prod_{k=1}^nF_k^{\sum_{d=1}^{\left\lfloor\!\frac nk\!\right\rfloor}\mu(d)\!\left\lfloor\!\frac n{dk}\!\right\rfloor\!\left\lfloor\!\frac m{dk}\!\right\rfloor} \\ = & \prod_{k=1}^n\prod_{d=1}^{\left\lfloor\!\frac nk\!\right\rfloor}F_k^{\mu(d)\!\left\lfloor\!\frac n{dk}\!\right\rfloor\!\left\lfloor\!\frac m{dk}\!\right\rfloor} \\ \end{aligned} \\ & \text{let}~T = dk,~\text{then} \\ & \begin{aligned} & ans \\ = & \prod_{T=1}^n\prod_{k|T}F_k^{\mu\left(\frac Tk\right)\!\left\lfloor\!\frac nT\!\right\rfloor\!\left\lfloor\!\frac mT\!\right\rfloor} \\ = & \prod_{T=1}^n\!\left(\prod_{k|T}F_k^{\mu\left(\frac Tk\right)}\!\right)^{\!\left\lfloor\!\frac nT\!\right\rfloor\!\left\lfloor\!\frac mT\!\right\rfloor} \\ \end{aligned} \\ & \text{let}~g(T) = \prod_{k|T}F_k^{\mu\left(\frac Tk\right)},~\text{then} \\ & ans = \prod_{T=1}^ng(T)^{\!\left\lfloor\!\frac nT\!\right\rfloor\!\left\lfloor\!\frac mT\!\right\rfloor}. \end{aligned} \]

然后 \(O(n\log n)\) 预处理 \(g\) 的前缀积,然后数论分块 \(O(\sqrt n)\) 求出答案。

代码