题解 P3935 【Calculating】

· · 题解

看到\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;
}