本来准备把莫比乌斯反演更完的，但是发现还需要有一些数论分块的知识，所以就写了这篇来讲数论分块。

先讲什么是数论分块。

引入1

求$[\frac{n}{i}]$$(1≤i≤n)$的所有可能值，$n≤10^9$。
看到的第一反应就是枚举，但是枚举时间复杂度太高了，肯定不行，那有没有什么能优化的办法呢？
先看$n=7$的情况：
$i=1:[\frac{7}{1}]=7$
$i=2:[\frac{7}{2}]=3$
$i=3:[\frac{7}{3}]=2$
$i=4:[\frac{7}{4}]=1$
$i=5:[\frac{7}{5}]=1$
$i=6:[\frac{7}{6}]=1$
$i=7:[\frac{7}{7}]=1$

发现了什么？$4-7$这一段全是$1$，也就是说这一段只要枚举一次就行了，那么大致的算法思路就出来了：
设$l,r$满足只有$l$到$r$的这一段满足$[\frac{n}{i}]=k$（$k=[\frac{n}{l}],l≤i≤r$），那么将$k$加进答案序列中去，然后让新一轮的$l$等于$r+1$。

重要难点

我们会发现在算法流程中每次只有$l$是上一轮定下来的，所以$r$是需要这一轮计算的，那么如何算呢？
先甩个式子，尝试感性理解一下：
$$r=\Bigg[\frac{n}{\big[\frac{n}{l}\big]}\Bigg]$$
严格证明：
$$[\frac{n}{l}]=[\frac{n}{r}]≤\frac{n}{r} \\\ \Leftrightarrow r≤\Bigg[\frac{n}{\big[\frac{n}{l}\big]}\Bigg] \\\ 又\because \Bigg[\frac{n}{\big[\frac{n}{l}\big]}\Bigg]能取到 \\\ \therefore r=\Bigg[\frac{n}{\big[\frac{n}{l}\big]}\Bigg]$$
在代码里就一句话：$r=n/(n/l)$

时间复杂度

对于每一块中的$i$，若$i≤[\sqrt{n}]$，则值必然只有$O(\sqrt{n})$个，否则，$[\frac{n}{i}]$最多也只有$O(\sqrt{n})$个，则总共最多有$O(2\sqrt{n})$个。

重点例题

例题一：洛谷UVA11526/AcWing 4585
模板题，直接套一遍数论分块的板子，结果发现对于每一部分只需要值乘以数量就可以了，具体看代码吧。

Code（代码很短，短的离谱）:

#include<bits/stdc++.h>
using namespace std;
int n; 
int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        int l=1,r,s=0;
        while(l<=n){
            r=n/(n/l);
            s+=(r-l+1)*(n/l);//将数量×值加到答案中
            l=r+1;
        }
        cout<<s<<endl;
    }
}

例题二：洛谷P2261
此题拿到的第一反应：我看错题了吧，这是数论分块？但是仔细一想，可以将式子变形：
$$\sum_{i=1}^n{kmodi} \\\ = \sum_{i=1}^n(k-i \times [\frac{k}{i}]) \\\ = \sum_{i=1}^nk - \sum_{i=1}^ni \times [\frac{k}{i}]) \\\ = nk - \sum_{i=1}^ni \times [\frac{k}{i}])$$
于是成功地将其化为了数论分块的形式，那么接下来如何求呢？
首先$nk$是已知数，所以只要求$\sum_{i=1}^ni \times [\frac{k}{i}])$就行了，还是一样的考虑方法，在确定$l,r$时考虑求$l+(l+1)+\dots+r$，易得$l+(l+1)+\dots+r=(l+r) \times (r-l+1) \div 2$，则这道题就结束了。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,k;
int main()
{
    LL l=1,r,s;
    cin>>n>>k;
    s=n*k;
    while(l<=min(n,k)){
        r=min(n,k/(k/l));
        s-=(l+r)*(r-l+1)/2ll*(k/l);
        l=r+1; 
    }
    cout<<s;
}

二维数论分块

引入2

求$[\frac{n}{i}]\times [\frac{m}{i}]$$(1≤i≤min(n,m))$的所有可能值，$n,m≤10^9$。
发现这个题跟引入$1$挺像，但是却是两个除法，那该如何做呢？
其实也很简单，令$r1=\Bigg[\frac{n}{\big[\frac{n}{l}\big]}\Bigg]$，$r2=\Bigg[\frac{m}{\big[\frac{m}{l}\big]}\Bigg]$，则$r=min(r1,r2)$，最后更新的时候只要令$l=r+1$即可。

所以学费了吗？

重要例题

洛谷P2260：简单提示：柿子可变形为：
$$\sum_{i=1}^n \sum_{j=1}^m (n mod i)(m mod j)（i!=j） = \sum_{i=1}^n(n mod i) \times \sum_{j=1}^m(m mod j)-\sum_{i=1}^{min(n,m)} (n mod i)(m mod i)$$
$19940417$不是个质数，所以还是用__int128吧。
建议自己手写一遍再看会好一些。

Code:

#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int mod=19940417;
int n,m,k;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?-1:1,ch=getchar();
    while('0'<=ch&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
void write(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int sol(int x)
{
    return x*(x+1)*(2*x+1)/6;
}
signed main()
{
    int s1=0,s2=0,s3=0; 
    n=read(),m=read();
    int l=1,r1,r2,r;
    s1=n*n;
    while(l<=n){
        r=n/(n/l);
        s1-=(l+r)*(r-l+1)/2*(n/l); 
        l=r+1;
    }
    s2=m*m;
    l=1;
    while(l<=m){
        r=m/(m/l);
        s2-=(l+r)*(r-l+1)/2*(m/l); 
        l=r+1;
    }
    k=min(n,m);
    s3=k*n*m;
    l=1;
    while(l<=k){
        r=min(k,n/(n/l));
        s3-=m*(l+r)*(r-l+1)/2*(n/l);
        l=r+1;
    }
    l=1;
    while(l<=k){
        r=min(k,m/(m/l));
        s3-=n*(l+r)*(r-l+1)/2*(m/l); 
        l=r+1;
    }
    l=1;
    while(l<=k){
        r1=min(k,n/(n/l));
        r2=min(k,m/(m/l));
        r=min(r1,r2);
        s3+=(sol(r)-sol(l-1))*(n/l)*(m/l);
        l=r+1;
    }
    s1%=mod,s2%=mod,s3%=mod;
    write((s1*s2%mod-s3+mod)%mod);
}