OceanEye's Blog

是时候表演真正的技术了!

@OceanEye6月前

04/13
21:39
OI

BZOJ4816 莫比乌斯反演

nlogn狄利克雷卷积打表

和普通的差不多,就是和换成积,贡献算一算就可以了

然后死活想不起来  写 O(n根号n) 的TLE到死

安利 jiry大爷 的教程

贴完代码跑路qwq

 

BZOJ4816 莫比乌斯反演

@OceanEye6月前

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