有了杜教筛的式子我们可以干很多事
[sum_{i=1}^nf*g(i)=sum_{i=1}^nf(i)sum_{j=1}^{lfloorfrac{n}{i}
floor}g(j)
]
对于这种两种形式的式子可以用杜教筛式子秒杀
[1.sum_{i=1}^nlfloorfrac{n}{i}
floor f(i)\
2.sum_{i=1}^nlfloorfrac{n}{i}
floor^2 f(i)
]
第一种式子
将杜教筛中(g())特殊化为(I():I(x)=1)得
[sum_{i=1}^nlfloorfrac{n}{i}
floor f(i)=sum_{i=1}^nI*f(i)
]
第二种式子
给(f())卷上(id():id(x)=x)得
[egin{align}
sum_{i=1}^nid*f(i)&=sum_{i=1}^nf(i)sum_{j=1}^{lfloorfrac{n}{i}
floor}id(j)\
&=sum_{i=1}^nf(i)frac{lfloorfrac{n}{i}
floor imes(lfloorfrac{n}{i}
floor+1)}{2}\
&=frac{sum_{i=1}^nlfloorfrac{n}{i}
floor^2 f(i)+sum_{i=1}^nI*f(i)}{2}
end{align}
]
[sum_{i=1}^nlfloorfrac{n}{i}
floor^2 f(i)=2 imessum_{i=1}^nid*f(i)-sum_{i=1}^nI*f(i)
]