蒟蒻以欧拉心算为例子,浅谈一下如何求一些较复杂的积性函数 欧拉心算: \[\sum_{i=1}^n\sum_{j=1}^n\phi(gcd(i,j))\] 与之前的一样: \[\sum_{d=1}^n\phi(d)\sum_{i=1}^{[n/d]}\sum_{j=1}^{[n/d]}[gcd(i,j)==1]\] 利用\(\mu\)函数的性质: \[\sum_{d=1}^n\phi(d)\sum_{i=1}^{[n/d]}\sum_{j=1}^{[n/d]}\sum_{k|gcd(i,j)}\mu(k)\] 然后: \[\sum_{d=1}^n\phi(d)\sum_{k=1}^{[n/d]}\mu(k)sum([n/kd])^2\] 其中\(sum(k)\)表示\(k*(k 1)/2\) 一般套路,设\(T=k*d\) 那么 \[\sum_{T=1}^n\sum_{d|T}\phi(d)*\mu(T/d)*sum([n/T])^2\] 于是我们现在的主要矛盾是要求出中间那一串。 有点像狄利克雷卷积 我们知道 \[F(T)=\sum_{d|T}\phi(d)*\mu(T/d)\] 这显然也是一个积性函数 我们主要的问题是如何用线性筛把它求出来,以维护一个前缀和 1.当\(T\)是质数的时候: \[F(T)=\phi(T)*\mu(1) \phi(1)*\mu(T)\] 于是: \[F(T)=T-2\] 2.当\(T=a*b\)其中\(gcd(a,b)==1\) 那么 \[F(T)=F(a)*F(b)\] 3.于是主要矛盾便成了当\(gcd(a,b)!=1\)时的情况,那么我们这时依 然要求出\(T\),我们记\(low(x)\)表示为\(x\)分解出来后最小质因子的最 大次方的数,例如:\(low(36)=2^2\) 大家知道线性筛筛素数每次每个数都是被自己的最小质因子筛掉的。 刚好,设当前为\(a\),最小质因子为\(p\) 那么: \[F(a*p)=F(a/low(a))*F(p*low(a))\] 但是有一一些特例: \[F(8)=F(4/low(4))*low(2*low(4))=F(1)*F(8)\] 当某个数刚好是某个质数的某次方时,这样的数似乎不行。 所以,我们在筛积性函数时,可以用这样的方法筛出来的前提就是: 1.当\(T\)为质数的时候可以快速得出 2.当\(T\)为\(p^k\)(\(p\)是质数)时可以快速得出,那么我们就可以用线 性筛得出积性函数的值了。 而这道题,\(F(p^k)\)是很好求了 最后就是这个\(low\)值,在线性筛的时候可以求出了 蒟蒻贴代码:
来源:https://www./content-4-434801.html
|
|