【BZOJ4816】【SDOI2017】数字表格

没看到正解先YY一下

题意要求

\(\prod_{i=1}^{n}\prod_{j=1}^{m}f((i,j))\)，其中\(f\)为fibnacci数列

改一下形式变成

\(\prod_{d=1}^{n}f(d)^{\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d]}\)

\(\prod_{d=1}^{n}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]}\)

\(\prod_{d=1}^{n}f(d)^{\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\)

然后就不会推了。。

然后听说直接根号算复杂度是\(n^{\frac{3}{4}}\)的。。

于是就可以直接过了。。（需要卡卡常