自动搬运

查看原文

来自洛谷，原作者为

	KesdiaelKen **

搬运于2025-08-24 21:54:19，当前版本为作者最后更新于2018-06-05 14:47:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到$\sum^r_{i=l}f(i)$，我们应该容易想到将它转化成$\sum^r_{i=1}f(i)-\sum^{l-1}_{i=1}f(i)$（容斥基本操作）。但是这个东西怎么求呢？

下面，我们引出两个定理和一个算法。

1.因数个数定理

设$n=p_1^{a_1}*p_2^{a_2}*...*p_m^{a_m}$，其中$p_1,p_2,...,p_m$均为互不相等的质数（$n$的质因数），则$n$的因数个数为$\prod_{i=1}^m{(a_i+1)}$。

证明：

设$n$的一个约数为$k$，则$k$必能表示为$p_1^{b_1}*p_2^{b_2}*...*p_m^{b_m}$，其中$\left\{{b_1,b_2,...,b_m} \right\}\in N$。则$b_i$的取值总共有$a_i+1$种。所以k的取值总共有$$\prod_{i=1}^m{(a_i+1)}$$

$$\mathcal{Q.E.D}$$

2.（我也不知道它叫什么名字）

设$f(x)$表示$x$的约数个数，求$\sum^n_{i=1}f(x)$。

解：

对于$f(x)$我们可以进行适当的转换得到一个与之相等的式子：$$\sum^n_{i=1}[i|x]$$

再对其进行转换：

$$\sum^n_{i=1}\sum^{\lfloor\frac{n}{i}\rfloor}_{j=1}[i*j==x] $$

看起来是更加复杂了。我们再将它带到原式中：

$$\sum^n_{i=1}f(x)=\sum^n_{x=1}\sum^n_{i=1}\sum^{\lfloor\frac{n}{i}\rfloor}_{j=1}[i*j==x]=\sum^n_{i=1}\sum^{\lfloor\frac{n}{i}\rfloor}_{j=1}=\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor $$

完成了转换。

3.整除分块

它的主要功能，就是将一个形如$\sum^n_{i=1}\lfloor\frac{n}{i}\rfloor$（当然不是只能在这个式子上应用，但它的确是最经常应用到整除分块的式子，没有之一）的式子的求值时间复杂度从$O(n)$降到$O(\sqrt n)$。

整除分块能实现基于这样一个事实：$\lfloor\frac{n}{i}\rfloor$的取值总共不会超过$2\sqrt n$种。为什么呢，我们来证明一下：

当$i<=\sqrt n$时：

我们需要证明：$\lfloor\frac{n}{i}\rfloor\not=\lfloor\frac{n}{i+1}\rfloor$

我们设$n\div i=k...s$，那么就有$n=i*k+s$。根据除法的性质，$s<i$，而又因为$i<=\sqrt n$，所以$k>=\sqrt n>=i$，所以$s<k$。

如果$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{i+1}\rfloor$，那么$n$就可以表示为$(i+1)*k+p$（$p>=0$），即$n=i*k+s+(k+p-s)=n+(k+p-s)$。而我们又知道$k-s>0,p>=0$。所以$k+p-s>0$，即等式两边矛盾。所以由反证法我们就得到了$\lfloor\frac{n}{i}\rfloor\not=\lfloor\frac{n}{i+1}\rfloor$。因此，在此情况下$\lfloor\frac{n}{i}\rfloor$的取值个数就等于$i$的取值数，即$\sqrt n$种。

当$i>\sqrt n$时：

这个不用怎么说了吧……$\lfloor\frac{n}{i}\rfloor_{max}$都已经是小于$\sqrt n$的了，总取值数当然不超过$\sqrt n$啊。

所以，两类加起来就是$2\sqrt n$种了。$$\mathcal{Q.E.D}$$

既然证玩了这个结论，我们就可以考虑这样一个思路：因为$\lfloor\frac{n}{i}\rfloor$的取值数为$\sqrt n$（那个$2$是常数，可以忽略），那么只要求出它取每一种值时$i$的最大值和最小值是多少，最终求和的时候用前缀和预处理算一下每一段的值是多少，加起来就可以了。

那么接下来，我们又需要证明一个结论了：

如果已知正整数$p,n$（$n>=p$），则使$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{p}\rfloor$的最大整数$i$的值就是$i_{max}=\lfloor\frac{n}{\frac{n}{p}}\rfloor$。

证明：

我们同样分类讨论一下。

当$p<=\sqrt n$时：

我们设$n\div p=k...s$，那么就有$n=p*k+s$。根据除法的性质，$s<p$，而又因为$p<=\sqrt n$，所以$k>=\sqrt n>=p$，所以$s<k$。而$\lfloor\frac{n}{p}\rfloor$的值就是$k$。

那么，就会有$\lfloor\frac{n}{\frac{n}{p}}\rfloor=\lfloor\frac{n}{k}\rfloor$。在此基础上，让我们再证明一个结论：$\lfloor\frac{n}{k}\rfloor=p$。我们令$n\div k=(p+t)...w$，则$n=p*k+t*k+w$。又因为$n=p*k+s$而，所以$n=p*k+t*k+w=n+(t*k+w-s)$，所以$t*k+w-s=0$。因为$k>w$且$k>=\sqrt n$，所以我们可以得出：$w,s\in[0,\sqrt n)$。所以：$(w-s)\in(-\sqrt n,\sqrt n)$。又因为$k>=\sqrt n$，所以$t$必须为$0$。所以$\lfloor\frac{n}{k}\rfloor=p$就证完了。而又由我们上面证的结论：$\lfloor\frac{n}{i}\rfloor$的取值总共不会超过$2\sqrt n$种可以知道当$p<=\sqrt n$的时候，所有$\lfloor\frac{n}{p}\rfloor$的值都不相同，即$p=i_{max}$。所以$i_{max}=\lfloor\frac{n}{\frac{n}{p}}\rfloor$，得证了。

当$p>\sqrt n$时：

我们设$n\div p=k...s$，那么就有$n=p*k+s$。根据除法的性质，$s<p$。而$\lfloor\frac{n}{p}\rfloor$的值就是$k$。

那么，就会有$\lfloor\frac{n}{\frac{n}{p}}\rfloor=\lfloor\frac{n}{k}\rfloor$。而我们现在要证明的，就是$\lfloor\frac{n}{k}\rfloor=i_{max}$。看上去很难证，但是我们注意到$i_{max}$必须符合且只需要符合的两个条件：$\lfloor\frac{n}{i_{max}}\rfloor=\lfloor\frac{n}{p}\rfloor=k,\lfloor\frac{n}{i_{max}+1}\rfloor\not=\lfloor\frac{n}{p}\rfloor=k$。那么，如果我们需要证明$\lfloor\frac{n}{k}\rfloor=i_{max}$，那么就只需要说明$\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=\lfloor\frac{n}{p}\rfloor=k\space\space and\space\space\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor+1}\rfloor\not=\lfloor\frac{n}{p}\rfloor=k$。看到$\lfloor\frac{n}{\lfloor\frac{n}{k}\rfloor}\rfloor=k$你想到了什么？

聪明的读者一定已经想到了，因为这个$k<\sqrt n$（讲了这么多这个不可能不会自行理解吧），所以这个结论在上面讨论$p<=\sqrt n$的时候已经证过了。所以，得证啦！

$$\mathcal{Q.E.D}$$

综合上面两个结论，我们便可以得出整除分块的思路了：

1. 令$i=1$

2. 对于当前的$i$求得$i_{max}$，设为$j$

3. 通过前缀和或公式（例如等差数列公式）求得函数（$\sum_{i=1}^nf(i)$中的$f(i)$）的自变量从$i$一直到$j$的函数值的总和，并且加进$sum$

4. 我们已知$\lfloor\frac{n}{j}\rfloor\not=\lfloor\frac{n}{j+1}\rfloor$，所以我们让$i=j+1$。如果现在的$i$仍然小于$n$，则跳转第$2$步，否则结束

最终得到的$sum$就是答案了。

综合上面的三项内容，思路就很明显了，相信各位如果仔细看了的话，一定已经完全明白这道题该怎么做了。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
using namespace std;
int main()
{
	long long left,right;
	scanf("%lld%lld",&left,&right);
	long long sum1=0,sum2=0;
	for(long long zuo=1,you;zuo<=right;zuo=you+1)
	{
		you=right/(right/zuo);
		sum1=(sum1+(right/zuo)%998244353*((you-zuo+1)%998244353)%998244353)%998244353;
	}
	for(long long zuo=1,you;zuo<=left-1;zuo=you+1)
	{
		you=(left-1)/((left-1)/zuo);
		sum2=(sum2+((left-1)/zuo)%998244353*((you-zuo+1)%998244353)%998244353)%998244353;
	}
	printf("%lld\n",((sum1-sum2)%998244353+998244353)%998244353);//熟练运用取余操作的一些技巧
	return 0;
}