Refact.ai Match 1 (Codeforces Round 985) |
---|
Закончено |
Вам дано натуральное число $$$k$$$ и множество $$$S$$$ всех целых чисел от $$$l$$$ до $$$r$$$ (включительно).
Вы можете выполнять следующую двухшаговую операцию любое количество раз (возможно, ноль):
Найдите максимально возможное количество раз, которое можно выполнить данную операцию.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит три целых числа $$$l$$$, $$$r$$$ и $$$k$$$ ($$$1\le l\le r\leq 10^9$$$, $$$1\leq k\le r-l+1$$$) — минимальное число в $$$S$$$, максимальное число в $$$S$$$ и параметр $$$k$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество раз, которое можно выполнить операцию из условия.
83 9 24 9 17 9 22 10 2154 220 2147 294 2998 24435 31 1000000000 2
2 6 0 4 0 1 7148 500000000
В первом наборе входных данных изначально $$$S = \{3,4,5,6,7,8,9\}$$$. Одна возможная оптимальная последовательность операций:
Во втором наборе входных данных изначально $$$S=\{4,5,6,7,8,9\}$$$. Одна возможная оптимальная последовательность операций:
В третьем наборе входных данных изначально $$$S=\{7,8,9\}$$$. Для каждого $$$x$$$ из $$$S$$$ в $$$S$$$ нет другого числа, кратного $$$x$$$ (кроме самого $$$x$$$). Поскольку $$$k = 2$$$, вы не можете выполнить никаких операций.
В четвертом наборе входных данных изначально $$$S=\{2,3,4,5,6,7,8,9,10\}$$$. Одна возможная оптимальная последовательность операций:
Название |
---|