CF1603D Artistic Partition

For two positive integers $ l $ and $ r $ ( $ l \le r $ ) let $ c(l, r) $ denote the number of integer pairs $ (i, j) $ such that $ l \le i \le j \le r $ and $ \operatorname{gcd}(i, j) \ge l $ . Here, $ \operatorname{gcd}(i, j) $ is the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ i $ and $ j $ . YouKn0wWho has two integers $ n $ and $ k $ where $ 1 \le k \le n $ . Let $ f(n, k) $ denote the minimum of $ \sum\limits_{i=1}^{k}{c(x_i+1,x_{i+1})} $ over all integer sequences $ 0=x_1 \lt x_2 \lt \ldots \lt x_{k} \lt x_{k+1}=n $ . Help YouKn0wWho find $ f(n, k) $ .

N/A

N/A

In the first test case, YouKn0wWho can select the sequence $ [0, 2, 6] $ . So $ f(6, 2) = c(1, 2) + c(3, 6) = 3 + 5 = 8 $ which is the minimum possible.