Number theory division block explanation example: 2021 Shaanxi Race C

introduce

Generally, an algorithm is introduced to solve a class of problems , So what is the problem ？

solve ：

The formula is very simple , Can directly seek , But if by even to the extent that Well , This is the time to introduce The concept of divisible partition .

This algorithm is not a sophisticated algorithm , Don't master any other knowledge to learn , Similar to greedy algorithms .

First of all, we can write a The brute force algorithm （ Almost all algorithms are extended by violence ）

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

It is concluded that the answer   yes ：20 10 6 5 4 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1, You found out The same number is a continuous segment

In fact, you can divide these numbers into several paragraphs , In each paragraph    It's all the same

and    The number of is    Grade , that The time complexity can be optimized to  

How to determine the left and right boundaries of each segment , It's very simple , Suppose the left boundary is , Then the right boundary is obviously  

And the next left boundary is Add... To the previous right boundary , The first left boundary is

This is a   Number theory is divided into blocks   stay OI wiki Explanation on ： Number theory divide into blocks

according to OI wiki Explanation on , We can know , Number theory is divided into blocks Can quickly calculate some containing The sum of division rounding down , Form like ：（ That's important , It can be extended , As long as the form is like this, it can be divided into blocks by integral division ）

When can     In time    or Has been pretreated     And   when , Number theory is divided into blocks   Can stay     Calculate the value of the above sum in the time .

The core ： take     The same number Package and calculate at the same time .

Code ：

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

Example ： The 9th Shaanxi ACM competition C--GCD（ I did the first division and partition ）
 

Title Description

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.

Input description :

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

Output description :

Print a single integer, indicating your answer.

Input

5 9 2

Output

3

explain

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.

The question ：

Ideas ：（ Notice below l and 1 The difference between ）

#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;
}