数论整除分块讲解 例题：2021陕西省赛C

引入

一般一个算法的引入都是为了解决一类问题，那么这个问题是什么？

求解：

式子很简单，可以直接 求，但是如果 为 甚至 呢，这个时候就要引入 整除分块的概念。

这个算法不能算是一种高深算法，不要掌握什么其他知识就能学，类似于贪心算法。

首先我们可以先写一个 暴力算法（任何算法几乎都是暴力引申的）

n = 20;
for (int i = 1; i <= n; i++) {
    printf("%d ", n / i);
}

得出的 答案 是：20 10 6 5 4 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1，你发现了 相同数是连续的一段

那么其实你就可以把这些数划分成若干段，每一段中的  的值都相同

而  的个数是  级别的，那么 时间复杂度就可以优化到 

如何确定每一段的左右边界呢，其实很简单，假设左边界是，那么右边界显然就是 

而下一个左边界是 上一个右边界加，最开始的左边界是

这是 数论分块 在 OI wiki 上的讲解：数论整除分块

根据 OI wiki 上的讲解，我们可以知道，数论分块 可以快速计算一些含有 除法向下取整的和式，形如：（这点很重要，是可以扩展的，只要形如此式就可以用整除分块求）

当可以在   时间内计算  或 已经预处理出   的前缀和 时，数论分块 就可以在   的时间内计算上述和式的值。

核心：将   相同的数打包同时计算。

代码：

for (int l = 1, r; l <= n; l = r + 1) {
	r = min(n, n / (n / l));//注意min
	ans += (r - l + 1) * (n / l);
}

例题：陕西省第九届ACM竞赛 C--GCD（我做的第一道整除分块）
 

题目描述

Bob is interested in GCDs (Greatest Common Divisors). Formally, for some positive integers (a1,...,ak), we denote gcd(a1​,...,ak​) as the greatest positive integer d, such that d∣ai for each 1≤i≤k

Bob has chosen an interval [l,r]. He is going to choose k distinct integers from the interval and compute their GCD. There are many integers that can be the final answer, and Bob is curious in the number of such integers. Please write a program to tell him the answer.

输入描述:

The first and only line of input consists of three integers l,r,k(1≤l≤r≤,2≤k≤r−l+1)

输出描述:

Print a single integer, indicating your answer.

输入

5 9 2

输出

3

说明

For the sample, it is possible to get 1,2,3 as the final GCD, by choosing numbers (7,9),(6,8) and (6,9). It turns out that any other integer cannot become the GCD, thus the answer is 3.

题意：

思路：（注意下图 l 和 1 的区别）

#include<bits/stdc++.h>

using namespace std;

#define int long long
int l, r, k;

bool check(int gcd) {
	return (r / gcd - (l - 1) / gcd) >= k;
}

signed main()
{
	cin >> l >> r >> k;
	int ans = 0;
	for (int i = 1, j; i <= r; i = j + 1)
	{
		if (i < l) j = min(r / (r / i), (l - 1) / ((l - 1) / i));
		else j = r / (r / i);
		ans += (j - i + 1) * (check(i));
	}
	cout << ans << '\n';

	return 0;
}