网站建设优秀网站建设,德州营销型网站,wordpress小工具源码,解析网站制作#6207. 米缇
推式子 ∑i1n∑j1ndK(ij)∑i1n∑j1n∑x∣i∑y∣j[gcd(x,y)1]ixkyk∑i1n∑j1n∑x∣i∑y∣j∑d∣gcd(x,y)μ(d)ixkyk∑d1nμ(d)dk∑i1nd∑x∣iixk∑j1nd∑y∣iyk∑d1nμ(d)dk∑i1nd∑x∣ixk∑j1nd∑y∣iyk∑d1nμ(d)dk(∑i1nd∑x∣ixk)2∑d1nμ(d)dk(∑x1ndxk∑x∣i…#6207. 米缇
推式子
∑i1n∑j1ndK(ij)∑i1n∑j1n∑x∣i∑y∣j[gcd(x,y)1]ixkyk∑i1n∑j1n∑x∣i∑y∣j∑d∣gcd(x,y)μ(d)ixkyk∑d1nμ(d)dk∑i1nd∑x∣iixk∑j1nd∑y∣iyk∑d1nμ(d)dk∑i1nd∑x∣ixk∑j1nd∑y∣iyk∑d1nμ(d)dk(∑i1nd∑x∣ixk)2∑d1nμ(d)dk(∑x1ndxk∑x∣i)2∑d1nμ(d)dk(∑x1ndxk∑x1nxd)2∑d1nμ(d)dk(∑i1ndiknid)2\sum_{i 1} ^{n} \sum_{j 1} ^{n} d_K(ij)\\ \sum_{i 1} ^{n} \sum_{j 1} ^{n} \sum_{x \mid i} \sum_{y \mid j} [gcd(x, y) 1]\frac{i}{x} ^ ky ^ k\\ \sum_{i 1} ^{n} \sum_{j 1} ^{n} \sum_{x \mid i} \sum_{y \mid j} \sum_{d \mid gcd(x, y)} \mu(d) \frac{i}{x} ^ ky ^ k\\ \sum_{d 1} ^{n} \mu(d) d ^ k \sum_{i 1} ^{\frac{n}{d}} \sum_{x \mid i} \frac{i}{x} ^ k \sum_{j 1} ^{\frac{n}{d}} \sum_{y \mid i} y ^ k\\ \sum_{d 1} ^{n} \mu(d) d ^ k \sum_{i 1} ^{\frac{n}{d}} \sum_{x \mid i} x ^ k \sum_{j 1} ^{\frac{n}{d}} \sum_{y \mid i} y ^ k\\ \sum_{d 1} ^{n} \mu(d) d ^ k (\sum_{i 1} ^{\frac{n}{d}} \sum_{x \mid i} x ^ k) ^ 2\\ \sum_{d 1} ^{n} \mu(d) d ^ k (\sum_{x 1} ^{\frac{n}{d}}x ^ k \sum_{x \mid i}) ^ 2\\ \sum_{d 1} ^{n} \mu(d) d ^ k (\sum_{x 1} ^{\frac{n}{d}}x ^ k \sum_{x 1} ^{\frac{n}{xd}}) ^ 2\\ \sum_{d 1} ^{n} \mu(d) d ^ k (\sum_{i 1} ^{\frac{n}{d}}i ^ k \frac{n}{id}) ^ 2\\ i1∑nj1∑ndK(ij)i1∑nj1∑nx∣i∑y∣j∑[gcd(x,y)1]xikyki1∑nj1∑nx∣i∑y∣j∑d∣gcd(x,y)∑μ(d)xikykd1∑nμ(d)dki1∑dnx∣i∑xikj1∑dny∣i∑ykd1∑nμ(d)dki1∑dnx∣i∑xkj1∑dny∣i∑ykd1∑nμ(d)dk(i1∑dnx∣i∑xk)2d1∑nμ(d)dk(x1∑dnxkx∣i∑)2d1∑nμ(d)dk(x1∑dnxkx1∑xdn)2d1∑nμ(d)dk(i1∑dnikidn)2
考虑求∑i1nμ(i)ik\sum\limits_{i 1} ^{n} \mu(i) i ^ ki1∑nμ(i)ik我们卷上IidkIid ^kIidk得到S(n)1−∑i2nikS(ni)S(n) 1 - \sum\limits_{i 2} ^{n} i ^ k S(\frac{n}{i})S(n)1−i2∑nikS(in)这一项可以通过拉格朗日插值跟杜教筛得到。
考虑求∑i1nikni\sum\limits_{i 1} ^{n} i ^ k \frac{n}{i}i1∑nikin我们可以通过数论分块加拉格朗日插值来求。
注意这题拉格朗日插值求值同样也上记忆化。
代码
待补......
