数论分块：应该算是一类思想

什么是数论分块

我对数论分块的理解就是：在一类要统计$\sum_{i}^{n}{f(i)}$的数学题中，由于$f(i)$是单调的，故存在$x,y \in [i,j]$使得$f(x)=f(y)$。于是只要找到这段区间就可以节省计算区间内每一个函数值的时间开销。

时间复杂度大抵是$O(\sqrt n)$的？

数论分块入门题

【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$】例一：bzoj1968: [Ahoi2005]COMMON 约数研究

Description

Input

Output

 题目分析

答案即为$1..x$的所有约数个数和。

我们知道换种形式答案就是$\sum_{i}^{}{⌊\frac{n}{i}⌋}$。

那么暴力算法来了：所以我们

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

就好了。

由于$n=10^6$，所以这个$O(n)$的算法是能够过去的。但是不行！这个是数论分块的板子题，我们怎么能够止步于$O(n)$的算法呢？

若用$g(i)$表示$\frac{n}{i}$，显然$ans=\sum_{i=1}^{n}{g(i)}$，并且$g(i)$是并不严格单调的。

自然而然地想到，在求$g(i)$的同时能不能够求出$[i,j]$呢？

这里有一个结论，$j=⌊{\frac{n}{⌊\frac{n}{i}⌋}}⌋$，下面来证明这个结论。

我们有 $j=⌊{\frac{n}{⌊\frac{n}{i}⌋}}⌋ \leq {\frac{n}{⌊\frac{n}{i}⌋}}<j+1$，因此得到

\begin{cases}⌊\frac{n}{i}⌋\leq \frac{n}{j}\\\frac{n}{j+1}<{⌊\frac{n}{i}⌋}\end{cases}

故$j$是满足条件的最大值。

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 
 4 int n;
 5 ll ans;
 6 
 7 int main()
 8 {
 9     register int i,j;
10     scanf("%d",&n);
11     for (i=1; i<=n; i=j+1)
12         j = n/(n/i),
13         ans += 1ll*(j-i+1)*(n/i);
14     printf("%lld\n",ans);
15     return 0;
16 }

【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$变式】例二：

题目描述

给定两个整数l和r。

对于任意x，满足 l≤x≤r，把x的所有约数全部写下来。

对于每个写下来的数，只保留最高位的那个数码。求[1,9]中每个数码出现的次数。

数据范围

对于100%的数据：$1≤l≤r≤10^9$

题目分析

这里略有不同的是，每个因数只保留最高位的数码，相当于就是答案贡献加在了不同的地方上。

很显然的是这个答案是可减的，于是我们就可以用类似前缀和的思想依次处理$[1,9]$。

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 
 4 int l,r;
 5 
 6 ll work(ll x, ll a, ll b)
 7 {
 8     ll ret = 0, j = 0;
 9     for (ll i=a; i<=b; i=j+1)
10         j = std::min(x/(x/i), b),
11         ret += 1ll*(j-i+1)*(x/i);
12     return ret;
13 }
14 ll get(ll x, ll p)
15 {
16     ll ret = 0, t = 1;
17     for (; x>=p; t*=10, p*=10)
18         ret += work(x, p, std::min(x, p+t-1));
19     return ret;
20 }
21 int main()
22 {
23     scanf("%d%d",&l,&r);
24     for (int i=1; i<=9; i++)
25         printf("%lld\n",get(r, i)-get(l-1, i));
26     return 0;
27  }

这里$get(x,p)$表示$1..x$个数中，因数最高位为$p$的答案总数。例如$p=3$，那么最高位为$p$的数一定是$300..399$,$3000...3999$这样的数。

之后的$work(x,a,b)$则表示$a..b$之间是$x$因数的个数。这一步就转变成了$\sum_{i}^{}{⌊\frac{n}{i}⌋}$的模型，于是就可以用数论分块做了。

至此看上去很奇怪的这道题就转化成了那个普通模型了。

【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$变式】例三：1257: [CQOI2007]余数之和

Description

Input

Output

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3  
 4 ll n,k,ans;
 5  
 6 int main()
 7 {
 8     register int i,j;
 9     scanf("%lld%lld",&n,&k);
10     ans = n*k;
11     for (i=1; i<=n; i=j+1)
12     {
13         if (!(k/i)) break;
14         j = std::min(k/(k/i), n);
15         ans -= 1ll*(j+i)*(j-i+1)/2*(k/i);
16     }
17     printf("%lld\n",ans);
18     return 0;
19 }