OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

@OceanEye7年前

04/11
23:03
OI

BZOJ2820

莫比乌斯反演

普通的莫比乌斯反演就是搞出一个分式然后利用[n/i]的连续性制造根号复杂度的东西啊= =

这里的推导也是一样的

先找到simple的f(x) & g(x)

f(x)=sigma(i)sigma(j) gcd(i,j)==x

g(x)=sigma(i)sigma(j) x|gcd(i,j)

上面这个东西随便反演吧= =然后把所有的质数尝试带进x里面

sigma(prime -> p) f(x) == sigma(prime -> p) sigma(dx<=p) g(dx) * μ(d)

把dx换成C,会发现一个C对应着几个 μ(d),这里是一个质因子对应一个 μ(d)。

这里把上面那行东西的值想成一个奇奇gaygay的数论函数h(C)就可以了。

【最神奇的是这个函数居然可以线性求= =太神了不仔细看都看不出来】

这里就可以对于1-N中的每个数来计算贡献了= =

即是 sigma(C = 1 to N) [N/C]*[M/C] * h(C)

然后套一套根号前缀和就可以了。

 

BZOJ2820