【数论分块】数论分块算法模板及真题

1.数论分块的含义

数论分块算法，就是枚举出使得取整函数发生变化的地方。
例如，对表达式 $\lfloor \frac{n}{i}\rfloor$使用数论分块算法，就可以在$O(\sqrt{n})$的时间复杂度下枚举所有满足$\lfloor \frac{n}{i-1}\rfloor +1=\lfloor \frac{n}{i}\rfloor$的 i 。

2.算法模板

long long r;
for(int l = 1; l <= n; l = r + 1)
{r = k/(k/l)；/*your code*/
}

变量 l 就是取整函数发生变化的位置，即满足$\lfloor \frac{n}{l-1}\rfloor +1=\lfloor \frac{n}{l}\rfloor$(l = 1除外）的位置，变量 r 就是满足 $\lfloor \frac{n}{x}\rfloor =\lfloor \frac{n}{l}\rfloor$的所有x 中最大的一个。
直观上，该过程时间复杂度小于 $O(n)$，因为每次往后跳的长度大于1，
该算法的实际复杂度为 $O(\sqrt{n})$。
正确性证明和时间复杂度证明，详见此处。写题不需要证明。

3.算法的优化点

将所有$\lfloor \frac{n}{i}\rfloor$结果一样的 i 一并取出，使得时间复杂度降为$O(\sqrt{n})$。
涉及取整的地方均可能用到此算法，包括但不限于，整除(练习题1）、最大公因数(练习题3)、最小公倍数(练习题2)、取模(本文例题）。

4.例题

P2261 [CQOI2007] 余数求和

题目描述

给出正整数 $n$ 和 $k$，请计算

$$G(n,k)=\sum _{i=1}^{n}k\mathrm{mod}i$$

其中 $k\mathrm{mod}i$ 表示 $k$ 除以 $i$ 的余数。

输入格式

输入只有一行两个整数，分别表示 $n$ 和 $k$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

10 5

输出 #1

29

说明/提示

样例 1 解释

$G(10,5)=0+1+2+1+0+5+5+5+5+5=29$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n,k\le 10^3$。
• 对于 $60\%$ 的数据，保证 $n,k\le 10^6$。
• 对于 $100\%$ 的数据，保证 $1\le n,k\le 10^9$。

---

解题思路

• $a\%b=a-\lfloor \frac{a}{b}\rfloor \ast b$
• 求和时，前半部分和后半部分，分开处理。
• 数列 $a_i=i\ast \lfloor \frac{x}{i}\rfloor$，在$\lfloor \frac{x}{i}\rfloor$为不变值的时候，是等差数列。

AC代码

#include<bits/stdc++.h>
#define int long longusing namespace std;
typedef pair<int,int> PII;
const int mod = 998244353;
void solve()
{int n,k;cin >> n >> k;long long ans = 0;ans += n*k;int r;for(int i = 1; i <= n; i = r + 1){if(k/i == 0) break;r = min(k/(k/i),n);ans -= (r-i+1)*(i+r)/2 *(k/i);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while(t --){solve();}
}

练习题

• 【AtCoder Regular Contest 150B】
• 【2025CCPC北京市赛】
• 【2021ICPC陕西省赛】