整数分块(真的会考吗)

对于形如 \(\sum_{i=1}^{n}\lfloor x/i \rfloor\) 的式子,我们有这么一个\(O(\sqrt n)\)的做法

别管证明了,我已经不是很记得了,反正形式很简单

for(int l=1,r;l<=n;l=r+1){
    if(k/l!=0)r=min(k/(k/l),n);
    else r=n;
    sum+=(r-l+1)*(k/l); 
}

当然式子什么的都会有一点的变形
稍微举例两个:

1.

这个就是\(\sum_{i=1}^{n}k-i*\lfloor k/i \rfloor\)
然后变一下: \(n*k-\sum_{i=1}^{n}i*\lfloor k/i \rfloor\)
所以说你还要考虑块长贡献的\(i\),为等差数列
粘份代码:

for(int l=1,r;l<=n;l=r+1){
    if(k/l!=0)r=min(k/(k/l),n);
    else r=n;
    sum+=(r-l+1)*(k/l)*(l+r)>>1; 
}

2.

Calculating

题目描述

若 \(x\) 分解质因数结果为 \(x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}\)，令\(f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)\)，求 \(\sum_{i=l}^rf(i)\) 对 \(998\,244\,353\)

相当于求约数个数的前缀和
直接考虑一个数会作为约数出现的次数
发现式子就是 \(\sum_{i=1}^{n}\lfloor n/i \rfloor\)
差分一下就结束了