我的blog懒得装latex了 附上蒟蒻我这篇的csdn链接

http://blog.csdn.net/elijahqi/article/details/79610235

 n<=1e9 给定一个模数 现场有13人AC..我..好菜啊 对原式化简 $\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{i} [gcd(i,j,k)==d]$ $\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{i} [gcd(i,j,k)==1]$ $\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{i}\varepsilon(gcd(i,j,k))$ $\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{i}\sum\limits_{d’|gcd(i,j,k)}^{}\mu(d’)$ $\sum\limits_{d=1}^{n}d\sum\limits_{d’=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d’)\sum\limits_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}\sum\limits_{j=1}^{i}\sum\limits_{k=1}^{i}1$ 设D为$d*d’$观察到后面为$\sum\limits_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}i^{2}$ 将前半部分替换卷积 后半部分替换公式 $\sum\limits_{D=1}^{n}\sum\limits_{d’|D}^{}\frac{D}{d’}\mu(d’)\frac{\lfloor\frac{n}{dd’}\rfloor*(\lfloor\frac{n}{dd’}\rfloor+1)*(2*\lfloor\frac{n}{dd’}\rfloor)}{6}$ $\sum\limits_{D=1}^{n}\varphi(D)\frac{\lfloor\frac{n}{dd’}\rfloor*(\lfloor\frac{n}{dd’}\rfloor+1)*(2*\lfloor\frac{n}{dd’}\rfloor)}{6}$ 因为后半部分可以考虑到分块计算所以只需要前半部分前缀和即可 那么杜教筛 预处理欧拉函数的前 2/3使得复杂度降为$n^{\frac{2}{3}}$ 顺带学习了发杜教筛 下面乘号部分代表卷积符号 考虑两个积性函数的卷积$(f*g)(n)=h$如何求积性函数前缀和 考虑$\varphi*1=id$ 顾前缀和可以表示为$\sum\limits_{i=1}^{n}i=\sum\limits_{i=1}^{n}\sum\limits_{d|i}^{}1(d)*\varphi(\frac{n}{d})$常见套路 $\sum\limits_{i=1}^{n}i=\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(i)$ $H[i]$表示$\varphi$的前缀和 那么显然$\frac{n*(n+1)}{2}=\sum\limits_{d=1}^{n}H(\frac{n}{d})$ $\frac{n*(n+1)}{2}\sum\limits_{d=2}^{n}H(\frac{n}{d})=H(n)$好了剩下部分可以递归搞了

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论