除法分块

背景

定义一个函数f，f(x)表示x的所有因子和，比如f(6)=12

对于求单个的f(x)很简单，但是如果求sum(f(i)) i in [a, b]呢？

朴素做法

最暴力的做法很容易就想到

ll sum = 0;
for(int i=a; i<=b; i++)
{
    for(int j=1; j*j<=i; j++)
    {
        if(i%j==0)
            sum += j;
        if(j*j != i)
            sum += j/i;
    }
}

这种做法实在是太慢了，时间复杂度是O(n*sqrt(n))

线性做法

对于一个因子L，在1～n这个范围里面，包含L这个因子的数字只有n/L(除法向下取整)这么多个

且1～n里面，最大的因子是n，所以我们枚举一下因子，每次累加L*n/L即可

int cal(int n)
{
    int sum = 0;
    for(int i=1; i<=n; i++)
    {
        sum += i*(n/i);
    }
    return sum;
}

cout<<cal(a) - cal(b-1)<<endl;

除法分块

当n非常大的时候，即便是线性做法也是不够快的，我们考虑求sum(f(i)) i in[1, 12]

根据上面说道，每个因子的出现次数为n/L，所以对于1~12这个范围来说，1~12因子出现的次数为[12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1]

我们注意到有连续的因子区间出现的次数是一样的，那么我们可不可以将出现次数相同的因子一起算呢？

我们只需要知道区间的左右端点就可以做到了

左端点l是容易的求的，左端点等于上一个右端点+1，左端点初始化为1

右端点呢？右端点为n/(n/l)(除法皆为向下取整)，为什么右端点是这样的？当然是打表找规律啦看看这篇证明。

所以我们很容易就能求得1～n的每个数字的因子和

ll cal(ll n)
{
    ll sum = 0;
    for(ll L=1, R; L<=n; L=R+1)
    {
        // 区间右端点
        R = n/(n/L);
        // n/L为这段区间每个因子的出现次数
        // 我们知道连续的因子区间构成了一个d=1的等差数列，所以这一段区间的因子和为
        // (L+R)*(R-L+1)/2
        // (首项+末项)*(区间长度)/2
        sum += (n/L) * (L+R)*(R-L+1)/2;
    }
    return sum;
}

// 求i in [a, b]的sum(f(i))
ll a, b;
cin>>a>>b;
cout<<cal(b) - cal(a-1)<<endl;

例题

codeforces gym101652 Fear Factoring

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
using namespace std;
 
 
ull cal(ull n)
{
	ull ans = 0;
	for(ull l=1, r; l<=n; l=r+1)
	{
		r = n/(n/l);
		ans += (n/l) * (l+r)*(r-l+1)/2;
	}
	return ans;
}
int main()
{
	IO;
	ull a, b;
	cin>>a>>b;
	cout<<cal(b) - cal(a-1)<<"\n";
	return 0;
}