数论分块

· · 算法·理论

什么是数论分块？

我们要给幼儿园的小朋友分苹果（平均分，多余的自己留着吃）：

数论分块其实就是发现：

对于一些不同的人数，每个小朋友分到的苹果数是一样的！

它有什么用呢？

题目描述：求出

\sum_{i=1}^{100} \lfloor \frac{100}{i} \rfloor

普通思路

直接暴力：

总运行次数：100 次。

数论分块

我们可以找到规律（关键点在后面）：

总运行次数：19 次。

乍一看是不是差距不大？但如果是计算 \sum_{i=1}^{10^{12}} \lfloor \frac{10^{12}}{i} \rfloor 呢？

简单例题

题目描述：输入 n，计算

\sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor

我们可以以 n 为 10 为例，画个表格：

i \lfloor \frac{10}{i} \rfloor
1 10
2 5
3 3
4 2
5 2
6 1
7 1
8 1
9 1
10 1

我们可以注意到，一些相同的值会连续出现好几次，特别是 1 和 2。这样的区间我们就叫它块。

计算步骤

#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans;
int main()
{
    scanf("%d",&n);
    for(l=1;l<=n;l=r+1)
    {
        int num=n/l;
        r=n/num;
        ans+=(r-l+1)*num;
    }
    printf("%d",ans);
    return 0;
}

时间复杂度分析

所以数论分块的时间复杂度是 O(\sqrt{n})。

余数求和

我们看一道题目：P2261。我们知道：

k \bmod i = k - \lfloor \frac{k}{i} \rfloor \times i

所以题目就变成了求：

\sum_{i=1}^{n} k - \lfloor \frac{k}{i} \rfloor \times i

把 k 提出来，得：

其中：

\sum_{i=1}^{n} \lfloor \frac{k}{i} \rfloor \times i

可以用数论分块求出来，剩下的就简单了。

代码

#include<bits/stdc++.h>
#define int long long//开long long
using namespace std;
int n,k,l,r,ans;
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(l=1;l<=n;l=r+1)
    {
        int num=k/l;
        if(num==0)
        break;
        r=min(k/num,n);
        ans+=((r-l+1)*(l+r)/2)*num;//这里不是区间长度了，而是l一直加到r，可以用等差数列求和公式
    }
    printf("%lld",n*k-ans);
    return 0;
}

高级用法

向上取整

输入 n，计算：

\sum_{i=1}^{n} \lceil \frac{n}{i} \rceil

我们知道：

\lceil \frac{n}{i} \rceil = \lfloor \frac{n+i-1}{i} \rfloor = \lfloor \frac{n-1}{i} \rfloor + 1

然后我们就可以正常数论分块了，但是要注意，在 l = n 的时候，会发生除以 0，需要特判。这个点卡了我半个小时。

上代码

#include<bits/stdc++.h>
using namespace std;
int n,l,r,ans=0;
int main()
{
    scanf("%d",&n);
    for(l=1;l<=n;l=r+1)
    {
        int num=(n-1)/l;
        if(l!=n)
        r=min((n-1)/num,n);
        else
        r=n;
        ans+=(num+1)*(r-l+1);
    }
    printf("%d",ans);
    return 0;
}

例题

看看我们的例题，求约数和的题。我们可以设 \operatorname{calc}(x) 表示：

\sum_{i=1}^{x} \operatorname{f}(i)

仔细一想就会发现我们可以枚举每一个可能的因数 i，一共有 \lfloor \frac{x}{i} \rfloor 个 i 的倍数。所以我们的 \operatorname{calc}(x) 就是：

\sum_{i=1}^{x} \lfloor \frac{x}{i} \rfloor \times i

我们的最终答案就是 \operatorname{calc}(y)-\operatorname{calc}(x-1)。

上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int l,r,ans;
int calc(int x)
{
    ans=0;
    for(l=1;l<=x;l=r+1)
    {
        int num=x/l;
        r=x/num;
        ans+=(l+r)*(r-l+1)/2*num;
    }
    return ans;
}
int x,y;
signed main()
{
    scanf("%lld%lld",&x,&y);
    printf("%lld",calc(y)-calc(x-1));
    return 0;
}

我们来看第二道题。乍一看很难，但其实跟上一题很类似。首先，根据因数个数定理，可以知道 \operatorname{f}(x) 其实就是 x 的因数个数。

那么我们同样的设 \operatorname{calc}(n) 表示 1 到 n 每一个数的因数个数之和。对于每一个可能的因数 i，会出现 \lfloor \frac{n}{i} \rfloor 次，所以我们可以用数论分块。

我们可以用前缀和的想法，我们的最终答案就是 \operatorname{calc}(r)-\operatorname{calc}(l-1)。代码其实跟上一题的几乎一样。

上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int ans;
int calc(int x)
{
    ans=0;
    for(int l=1,r;l<=x;l=r+1)
    {
        int num=x/l;
        r=x/num;
        ans+=(r-l+1)*num;
    }
    return ans;
}
int l,r;
signed main()
{
    scanf("%lld%lld",&l,&r);
    printf("%lld",(calc(r)-calc(l-1))%mod);
    return 0;
}

给大家补充个 二维数论分块。

我们在二维数论分块中什么叫做一个块呢？我们在这里把 \lfloor \frac{n}{i} \rfloor 和 \lfloor \frac{m}{i} \rfloor 都一样的那个区间。那么我们主要改两个部分：

#include<bits/stdc++.h>
#define int long long//不开 long long 见祖宗
using namespace std;
int n,m,l,r,t,ans;
signed main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans=0;//不要忘记初始化
        scanf("%lld%lld",&n,&m);
        for(l=1;l<=min(n,m);l=r+1)
        {
            int num=(n/l)*(m/l);
            int r1=n/(n/l);//只看n/l
            int r2=m/(m/l);//只看m/l
            r=min(r1,r2);
            r=min(r,n);//防止超过n，不然后面更新答案会有问题
            ans+=(r-l+1)*num;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

数论分块虽然刚开始觉得难，但是做了几道例题后就能大概熟悉它的套路了。