本文主要是介绍[LibreOJ Round #11]Misaka Network 与求和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Misaka Network 与求和
题解
敢信,笔者第一眼把misaka看出了mikasa,如果不是后面还有个network
一看到这道题就知道是一道很烦人的数学题。
先应该很容易想到莫比乌斯反演。
原式可化为
= ∑ d = 1 n f ( d ) k ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ n d ⌋ [ ( i , j ) = 1 ] =\sum_{d=1}^{n}f(d)^k\sum_{i=1}^{\left\lfloor\frac{n}{d} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{d}\right \rfloor}[(i,j)=1] =∑d=1nf(d)k∑i=1⌊dn⌋∑j=1⌊dn⌋[(i,j)=1]
= ∑ d = 1 n f ( d ) k ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ n d ⌋ ∑ t ∣ ( i , j ) μ ( t ) =\sum_{d=1}^{n}f(d)^k\sum_{i=1}^{\left\lfloor\frac{n}{d} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{d}\right \rfloor}\sum_{t|(i,j)}\mu(t) =∑d=1nf(d)k∑i=1⌊dn⌋∑j=1⌊dn⌋∑t∣(i,j)μ(t)
= ∑ t = 1 n ∑ d = 1 ⌊ n t ⌋ f ( t ) k μ ( d ) ⌊ n t d ⌋ 2 =\sum_{t=1}^{n}\sum_{d=1}^{\lfloor\frac{n}{t}\rfloor}f(t)^k\mu(d)\left \lfloor\frac{n}{td}\right\rfloor^2 =∑t=1n
这篇关于[LibreOJ Round #11]Misaka Network 与求和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!