整除分块学习笔记

整除分块主要是用来求这么一个柿子的：

$\sum\limits_{i=1}^n \lfloor \dfrac{n}{i}\rfloor$

这个东西在 $n$ 很小的情况下是可以暴力做的，但是如果 $n$ 太大就不行了。

首先我们先打表找一下规律，输出一下 $n=30$ 时 $\lfloor\dfrac{n}{i}\rfloor$ 的值：

30 15 10 7 6 5 4 3 3 3 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

很容易发现，整个序列是单调不增的，而且会出现一些很长的值相同的连续段。

那么我们可以考虑每个连续段里的点的贡献一起计算，假设我们现在已经知道一个块的左端点为 $l$，那么我们只需要求出这个块的右端点 $r$ 就行了。

我们推一下柿子：

$\because \lfloor\dfrac{n}{r}\rfloor=\lfloor\dfrac{n}{l}\rfloor$

$\therefore \lfloor\dfrac{n}{l}\rfloor\le\dfrac{n}{r}<\lceil\dfrac{n}{l}\rceil$

省略上界：

$\dfrac{n}{r}\ge\lfloor\dfrac{n}{l}\rfloor$

两边同时取倒数，得：（不等式要变号）

$\dfrac{r}{n}\le\dfrac{1}{\lfloor\dfrac{n}{l}\rfloor}$

两边同时乘上 $n$，得：

$r\le\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}$

$\because r \color{Black}\colorbox{White}{是整数，且} r \color{Black}\colorbox{White}{最大}$

$\therefore r=\left\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\right\rfloor$

所以可以得出，如果一个块的左端点是 $l$，那么右端点就是 $\left\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\right\rfloor$。

我们考虑推广一下它，易得出如果要求

$\sum\limits_{i=1}^n \lfloor \dfrac{k}{i}\rfloor$

的话，左端点为 $l$ 的块的右端点是 $\min(n,\left\lfloor\dfrac{k}{\lfloor\dfrac{k}{l}\rfloor}\right\rfloor)$。

那么这样做的时间复杂度是多少的呢？很明显是 $O(\sqrt k)$ 的，因为 $\lfloor\dfrac{k}{i}\rfloor$ 只有 $\sqrt k$ 种取值，所以也就只有 $\sqrt k$ 个块。

现在我们来看一道例题：(P2261 [CQOI2007]余数求和)

求 $\operatorname{G}(n,k)=\sum\limits_{i=1}^n k\mod i$

推一下柿子：

$\sum\limits_{i=1}^n k\mod i$

$=\sum\limits_{i=1}^n k-i\lfloor\dfrac{k}{i}\rfloor$

$=nk-\sum\limits_{i=1}^n i\lfloor\dfrac{k}{i}\rfloor$

现在问题变为要求 $\sum\limits_{i=1}^n i\lfloor\dfrac{k}{i}\rfloor$ 的值了。我们可以运用刚刚的结论，求出每一个块的左右端点后，用 $\dfrac{k}{l}$ 乘上 $\sum\limits_{i=l}^r i$。$\sum\limits_{i=l}^r i$ 很显然可以 $O(1)$ 求出来。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

long long n,k;

inline long long getsum(long long l,long long r)
{
	return (l+r)*(r-l+1)/2;
}

int main()
{
	scanf("%lld%lld",&n,&k);
	long long ans=0;
	for(long long l=1;l<=n&&k/l>0;) // 如果 k/l=0，那么会 RE，仔细想想，这个块肯定是对答案没贡献的，所以直接跳出循环 
	{
		long long r=min(k/(k/l),n); // 记得取 min 
		ans+=getsum(l,r)*(k/l);
		l=r+1;
	}
	printf("%lld\n",k*n-ans);
	return 0;
}

再看一道进阶版的题：

P2260 [清华集训2012]模积和

首先我们令 $n$ 为 $n,m$ 中较小的一个，$m$ 为另一个。

推一下柿子，不难得出：（推柿子还是自己推推比较好，给个思路：总体减去 $i=j$ 的，实在不行可以看 这里）

$\color{Black}\colorbox{White}{原式}=\operatorname{F}(n)\operatorname{F}(m)-n^2m+n\operatorname{G}(n,m)+m\operatorname{G}(n,n)-\sum\limits_{i=1}^n i^2\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor$

其中：

$\operatorname{G}(n,k)=\sum\limits_{i=1}^n i\lfloor\dfrac{k}{i}\rfloor$

$\operatorname{F}(n)=\sum\limits_{i=1}^n n-i\lfloor\dfrac{n}{i}\rfloor=n^2-\operatorname{G}(n,n)$

现在考虑求解 $\sum\limits_{i=1}^n i^2\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor$，容易发现，$\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor$ 是单调不增的，所以可以使用数论分块，左端点为 $l$ 的块右端点就是 $\min(\left\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\right\rfloor,\left\lfloor\dfrac{m}{\lfloor\dfrac{m}{l}\rfloor}\right\rfloor)$，$i^2$ 的和则可以使用公式来求解。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const long long mod=19940417,inv2=9970209,inv6=3323403;

long long n,m;

inline long long G(long long n,long long k)
{
	long long res=0;
	for(long long l=1;l<=n&&k/l>0;)
	{
		long long r=min(k/(k/l),n);
		res+=(l+r)*(r-l+1)%mod*inv2%mod*(k/l)%mod;
		res%=mod;
		l=r+1;
	}
	return res;
}

inline long long F(long long n)
{
	return (((n*n%mod-G(n,n))%mod)+mod)%mod;
}

inline long long sum(long long x) // 小学奥数的知识：1^2+2^2+3^2+...+x^2 
{
	return x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	if(n>m)
	{
		long long t=n;
		n=m;
		m=t;
	}
	long long ans=F(n)*F(m)%mod-n*n%mod*m%mod+n*G(n,m)%mod+m*G(n,n)%mod; // 疯狂取模，少一个可能就会 WA 
	ans=(ans%mod+mod)%mod;
	for(long long l=1;l<=n;)
	{
		long long r=min(n/(n/l),m/(m/l));
		ans-=((sum(r)-sum(l-1))%mod+mod)%mod*(n/l)%mod*(m/l)%mod;
		ans=(ans%mod+mod)%mod;
		l=r+1;
	}
	printf("%lld\n",ans);
	return 0;
}

练习题目

UVA11526 H(n)

P3935 Calculating