87 lines
2.3 KiB
Markdown
87 lines
2.3 KiB
Markdown
|
# A. Set
|
|||
|
|
|
|||
|
|
[Codeforces](https://codeforces.com/contest/2029/problem/A)
|
|||
|
|
|
|||
|
|
You are given a positive integer `k` and a set `S` of all integers from `l` to `r` (inclusive).
|
|||
|
|
|
|||
|
|
You can perform the following two-step operation any number of times (possibly zero):
|
|||
|
|
|
|||
|
|
First, choose a number `x` from the set `S`, such that there are at least `k` multiples of `x` in `S`
|
|||
|
|
(including `x` itself);
|
|||
|
|
|
|||
|
|
Then, remove `x` from `S` (note that nothing else is removed).
|
|||
|
|
|
|||
|
|
Find the maximum possible number of operations that can be performed.
|
|||
|
|
|
|||
|
|
|
|||
|
|
## Input
|
|||
|
|
|
|||
|
|
Each test contains multiple test cases. The first line of the input contains a single integer `t`
|
|||
|
|
(1 ≤ `t` ≤ 104) — the number of test cases. The description of test cases follows.
|
|||
|
|
|
|||
|
|
The only line of each test case contains three integers `l`, `r`, and `k` (1 ≤ `l` ≤ `r` ≤ 109, 1 ≤ `k` ≤ `r` − `l` + 1) — the minimum integer in `S`, the maximum integer in `S`, and the parameter `k`.
|
|||
|
|
|
|||
|
|
|
|||
|
|
## Output
|
|||
|
|
|
|||
|
|
For each test case, output a single integer — the maximum possible number of operations that can be performed.
|
|||
|
|
|
|||
|
|
|
|||
|
|
## Example
|
|||
|
|
|
|||
|
|
Input
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
8
|
|||
|
|
3 9 2
|
|||
|
|
4 9 1
|
|||
|
|
7 9 2
|
|||
|
|
2 10 2
|
|||
|
|
154 220 2
|
|||
|
|
147 294 2
|
|||
|
|
998 24435 3
|
|||
|
|
1 1000000000 2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Output
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
2
|
|||
|
|
6
|
|||
|
|
0
|
|||
|
|
4
|
|||
|
|
0
|
|||
|
|
1
|
|||
|
|
7148
|
|||
|
|
500000000
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
|
|||
|
|
## Note
|
|||
|
|
|
|||
|
|
In the first test case, initially, S={3,4,5,6,7,8,9}.
|
|||
|
|
|
|||
|
|
One possible optimal sequence of operations is:
|
|||
|
|
|
|||
|
|
- Choose x=4 for the first operation, since there are two multiples of 4 in S: 4 and 8. S becomes equal to {3,5,6,7,8,9};
|
|||
|
|
- Choose x=3 for the second operation, since there are three multiples of 3 in S: 3, 6, and 9. S becomes equal to {5,6,7,8,9}.
|
|||
|
|
|
|||
|
|
In the second test case, initially, S={4,5,6,7,8,9}. One possible optimal sequence of operations is:
|
|||
|
|
|
|||
|
|
- Choose x=5, S becomes equal to {4,6,7,8,9};
|
|||
|
|
- Choose x=6, S becomes equal to {4,7,8,9};
|
|||
|
|
- Choose x=4, S becomes equal to {7,8,9};
|
|||
|
|
- Choose x=8, S becomes equal to {7,9};
|
|||
|
|
- Choose x=7, S becomes equal to {9};
|
|||
|
|
- Choose x=9, S becomes equal to {}.
|
|||
|
|
|
|||
|
|
In the third test case, initially, S={7,8,9}. For each x in S, no multiple of x other than x itself can be found in S.
|
|||
|
|
Since k=2, you can perform no operations.
|
|||
|
|
|
|||
|
|
In the fourth test case, initially, S={2,3,4,5,6,7,8,9,10}. One possible optimal sequence of operations is:
|
|||
|
|
|
|||
|
|
- Choose x=2, S becomes equal to {3,4,5,6,7,8,9,10};
|
|||
|
|
- Choose x=4, S becomes equal to {3,5,6,7,8,9,10};
|
|||
|
|
- Choose x=3, S becomes equal to {5,6,7,8,9,10};
|
|||
|
|
- Choose x=5, S becomes equal to {6,7,8,9,10}.
|