Codeforces Round 752 (Div. 1) |
---|
Закончено |
Для двух положительных целых чисел $$$l$$$ и $$$r$$$ ($$$l \le r$$$) обозначим за $$$c(l, r)$$$ количество пар целых чисел $$$(i, j)$$$ таких, что $$$l \le i \le j \le r$$$ и $$$\operatorname{gcd}(i, j) \ge l$$$. Здесь $$$\operatorname{gcd}(i, j)$$$ обозначает наибольший общий делитель (НОД) чисел $$$i$$$ и $$$j$$$.
У вас есть два целых числа $$$n$$$ и $$$k$$$, где $$$1 \le k \le n$$$. Пусть $$$f(n, k)$$$ обозначает минимум $$$\sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})}$$$ по всем последовательностям из целых чисел $$$0=x_1 \lt x_2 \lt \ldots \lt x_{k} \lt x_{k+1}=n$$$.
Помогите YouKn0wWho найти $$$f(n, k)$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — количество наборов входных данных.
Первая и единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).
Для каждого набора входных данных выведите одно целое число — $$$f(n, k)$$$.
4 6 2 4 4 3 1 10 3
8 4 6 11
В первом наборе входных данных YouKn0wWho может выбрать последовательность $$$[0, 2, 6]$$$. Тогда $$$f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8$$$, что является минимально возможным.
Название |
---|