整除分块入门

未分类
10k 词

整除分块

首先引入一个问题，若我们要求这么一个式子：

自然而然会想到这么一段翻译代码：

1
2
for(int i=1;i<=n;i++)
  sum+=n/i;

但是，如果 $1\le n\le10^9$，又该如何解决呢？

显然，$\left\lfloor\dfrac{n}{i}\right\rfloor$与$\dfrac{n}{i}$的不同在于，前者的值在某些情况下会出现区间性的大量重复。
下面我们来考察当 $n=10$时$\left\lfloor\dfrac{n}{i}\right\rfloor$的取值

我们可以发现：

显然重复部分（我们将他们成为块）占比很大，因此我们就找到了优化的突破口，如何优化在重复部分耗费的计算？

由于 $i$ 单调递增排列，因此重复部分是连续出现的，对于一个块$[l,r]$，若求出了 $l,r$就可以快速计算一整个块整除意义上的贡献。

经过思考可以得到$l$的初值必定为$1$，还有一个很显然的$l$ 的转移方程：

此时问题再次简单化，如何在已知$l$的情况下，快速求出重复部分右端点 $r$？

考虑 $r$的性质：根据$[l,r]$的定义可以得到$\left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{r}\right\rfloor$，我们将$\left\lfloor\dfrac{n}{l}\right\rfloor$表示为$k$ 。
此时有：

此时若使 $r$ 最大，则取等，即
此时，我们已经得到了快速求出 $l,r$的算法,因此对于大量的重复贡献，我么可以利用$[l,r]$区间快速得到总贡献，时间复杂度为$\Theta(\sqrt{n})$。
具体实现请看代码：

1
2
3
4
5
6
for(int l=1,r;l<=n;l=r+1)
{
  int k=n/l;
  r=n/k;
  sum=sum+(k*(r-l+1));  //相同贡献乘区间长度
}

我们习惯把以上优化算法称为整除分块（或除法分块、数论分块等），它可以优化以下类似式子的时间复杂度：

例题深化

1. UVA11526

模板题，翻译都不需要的那种，直接整除分块优化。（过~~~）

2.P3935 Calculating

题目大意：求

首先我们要知道 $n=p_1^{c_1}\cdot p_2^{c_2}\cdots p_m^{c_m},则f(n)=(c_1+1)\cdot(c_2+1)\cdots(c_m+1)$即为$n$的因数个数，可以由质因数的组合得到这个公式，这里不再详解。

回顾到这道题，要求区间$[l,r]$中的数的因子个数之和，自然而然就是类似于前缀和式的方法：求出$[1,l-1]$的因子和以及$[1,r]$的因子和，然后后者减去前者，就可以得到$[l,r]$的因子和。

可以知道，$[1,n]$中$i$的倍数有$\left\lfloor\dfrac{n}{i}\right\rfloor$个，即有$\left\lfloor\dfrac{n}{i}\right\rfloor$个数包含因子$i$。因此$\sum\limits_{i=1}^{n}f(i)=\sum\limits_{i=1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor$

然后又变成了整除分块裸题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;
int a,b;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>a>>b;
    int suma=0,sumb=0;
    for(int l=1,r;l<=(a-1);l=r+1)
    {
      r=(a-1)/((a-1)/l);
      suma=(suma+(((a-1)/l)%MOD*(r-l+1)%MOD)%MOD)%MOD;
    }
    for(int l=1,r;l<=b;l=r+1)
    {
      r=b/(b/l);
      sumb=(sumb+((b/l)%MOD*(r-l+1)%MOD)%MOD)%MOD;
    }
    cout<<((sumb-suma)%MOD+MOD)%MOD;
	return 0;
}

3.CF616E Sum of Remainders

题目大意：
求

很简单的一道推式子题，就是因为用上了整除分块才水上了紫。

由于块中的元素重复，我们可以提取公因数，因此乘 $i$可以在整除分块的过程中执行，不会影响效率，$\sum\limits_{i=1}^{m}\left\lfloor\dfrac{n}{i}\right\rfloor i$可以利用整除分块和高斯求和公式快速得到（不懂得可以停下来稍微想想）。

照水不误

  • 运算过程中会爆longlong，取余很恶心
  • 在这种恶心超大取余数论题中，常要预处理出某些除数的乘法逆元。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define int long long
#define inv2 500000004//2在mod 1e9+7 意义下的乘法逆元
using namespace std;
int n,m;
int ans;
const int MOD=1e9+7;
signed main()
{
  cin>>n>>m;
  ans=((n%MOD)*(m%MOD))%MOD;
  int sum=0;
  for(int l=1,r;l<=min(n,m);l=r+1)
  {
    r=n/(n/l);
    if(r>m) r=m;
    sum=(1ll*sum%MOD+(1ll*(n/l)%MOD*((((r-l+1)%MOD)*((r+l)%MOD))%MOD*inv2%MOD)%MOD)%MOD)%MOD;
  }
  cout<<((ans-sum%MOD)%MOD+MOD)%MOD;
  return 0;
}

4.P2260 [清华集训2012]模积和

题目大意： 求

$\bmod 19940417$的值

对于这种式子很长，没有思路的题目，往往需要我们将式子拆开来才能找到考点。
考虑式子条件$i\ne j$的运算意义，就是在原有式子的基础上减去$i,j$重复部分，即

然后我们就可以愉快的手撕$\sum$:

我们使$m<n$:

这个式子结构性就很强了，我们可以考虑逐一求得式子各部分的值来得到最终答案。

  • part 1：$\sum\limits_{i=1}^{n}(n\bmod i)\sum\limits_{j=1}^{m}(m\bmod j)$
    很显然就是上一题的结论与做法，不再赘述。

  • part 2：$nm^2$
    入门级运算

  • part 3：$m\sum\limits_{i=1}^m\left\lfloor\dfrac{n}{i}\right\rfloor i+n\sum\limits_{i=1}^{m}\left\lfloor\dfrac{m}{i}\right\rfloor i$
    依旧是上一题结论，换汤不换药。

  • part 4：$\sum\limits_{i=1}^{m}\left\lfloor\dfrac{m}{i}\right\rfloor\left\lfloor\dfrac{n}{i}\right\rfloor i^2$

看到这个式子我一开始就蒙了（太弱了），是不是式子柴得不够完全啊，然后就浪费了大量的时间来化简这个式子，最后还是做了无用功。

那到底应该如何处理呢？观察这部分式子，$\left\lfloor\dfrac{m}{i}\right\rfloor$与$\left\lfloor\dfrac{n}{i}\right\rfloor$都是我们熟悉的整除分块，但是要是将他们联系在一起$\left\lfloor\dfrac{m}{i}\right\rfloor\left\lfloor\dfrac{n}{i}\right\rfloor$显然不是简单的直接分块相乘，那又该如何优化呢？借助上一题的思路，利用块的优化过程自然也要带上计算$i^2$，那是否 $\sum\limits_{i=1}^{n}i^2$也具有类似等差数列一样的求和公式呢（我太弱了不知道，在教练的帮助下推了好久才推出来）？

我们来模拟一下$\sum\limits_{i=1}^{m}\left\lfloor\dfrac{m}{i}\right\rfloor\left\lfloor\dfrac{n}{i}\right\rfloor$的过程,考虑$n=20,m=17$

稍加思索可以发现，$\left\lfloor\dfrac{n}{i}\right\rfloor$所分的一个块与$\left\lfloor\dfrac{m}{i}\right\rfloor$所分的一个块的交集（公共部分）也是$\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor$的一个块。

稍微数学一点的表达：

有了这个概念，我们就易得$\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor$的块$[l,r]$的左右端点转移方程：

接下来我们考虑推导 $S_n=\sum\limits_{i=1}^ni^2$ 的通项式。

考虑

此时，我们已经解决了关于这道题的所有难点，有了二维整除分块以及$\sum\limits_{i=1}^ni^2$的求和公式，我么就可仿照类似上一题一般的方法优化$\sum\limits_{i=1}^m\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor i^2$。

此时，我们首先化简题目的式子，然后对式子各部分进行逐一处理优化，最后得到了最终的算法：

处理以下函数

  • $F_x：\sum\limits_{i=1}^x(x\bmod i)$
  • $G_{x,y} ：\sum\limits_{i=1}^x(y\bmod i)$
  • $T：\sum\limits_{i=1}^m\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor i^2$

最终答案为：$F_nF_m-nm^2+nG_{m,m}+mG_{m,n}-T$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define int long long
const long long MOD=19940417,inv6=3323403,inv2=9970209;  //预处理公式中除数的乘法逆元
using namespace std;
int n,m;
int G(int s,int t)
{
  int sum=0;
  for(int l=1,r;l<=s;l=r+1)
  {
    r=min(t/(t/l),s);
    sum=(sum+1ll*(t/l)*(r+l)%MOD*(r-l+1)%MOD*inv2)%MOD;
  }
  return sum%MOD;
}
int F(int s)
{
  return (1ll*s*s-G(s,s))%MOD;
}
int S(int s)
{
  return 1ll*s*(s+1)%MOD*(s+s+1)%MOD*inv6%MOD;
}
int ans()
{
  int a;
  a=1ll*F(n)*F(m)%MOD;
  a=(a+1ll*n*G(m,m)+1ll*m*G(m,n))%MOD;
  a=1ll*(a-1ll*m*m%MOD*n)%MOD;
  return a;
}
int T()
{
  int sum=ans();
  for(int l=1,r;l<=m;l=r+1)
  {
    r=min(n/(n/l),m/(m/l));
    sum=(sum-1ll*((n/l)%MOD*(m/l))%MOD*(S(r)-S(l-1))%MOD)%MOD;
  }
  return (sum%MOD+MOD)%MOD;
}
signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin>>n>>m;
  if(m>n) swap(m,n);
  cout<<T();
  return 0;
}