[BZOJ4816/Luogu3704][Sdoi2017]数字表格(莫比乌斯反演,数论分块)

发布于 2018-01-21  206 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4816/Luogu3704][Sdoi2017]数字表格(莫比乌斯反演,数论分块)

Description

Doris刚刚学习了fibonacci数列。用f[i]表示数列的第i项,那么
f[0]=0
f[1]=1
f[n]=f[n-1]+f[n-2],n>=2
Doris用老师的超级计算机生成了一个n×m的表格,第i行第j列的格子中的数是f[gcd(i,j)],其中gcd(i,j)表示i,j的最大公约数。Doris的表格中共有n×m个数,她想知道这些数的乘积是多少。答案对10^9+7取模。

Http

BZOJ
Luogu

Tag

莫比乌斯反演,数论分块

题目大意

求\(\prod_{i=1}^{n} \prod_{j=1}^{m} fab(gcd(i,j))\)

解决思路

依照惯例,提取出\(d=gcd(i,j)\),则
\[Ans=\prod_{d=1}^{n} fab(d)^{\sum_{i=1}^{n} \sum{j=1}^{m} [gcd(i,j)==1]}\]
\(fab(d)\)的指数可以根据莫比乌斯反演变成
\[Ans=\prod_{d=1}^{n} fab(d)^{\sum_{i=1}^{n/d} \mu(i) \lfloor \frac{n}{id} \rfloor \lfloor \frac{m}{id} \rfloor }\]
令\(T=id\),把\(T\)提出来,得到
\[ Ans=\prod_{T=1}^{n} [\prod_{i|T} fab(\frac{T}{i})^{\mu(i)}]^{\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor} \]
里面这个东西并不是积性函数,怎么办呢?
考虑到\(n\)只有\(10^6\),可以\(O(n*log_{2}n)\)暴力算,提前处理好斐波那契数列和其逆元即可。
那么设\(H(x)=\prod_{i|x} f(\frac{x}{i})^{\mu(i)}\),求出它的前缀积和前缀积的逆元即可数论分块了

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4816/Luogu3704][Sdoi2017]数字表格(莫比乌斯反演,数论分块)


HNCJ OIer