Artistic Partition
Contest: Codeforces Round 752 (Div. 1)
Difficulty rating: 3000
Tags: divide and conquer, dp, number theory

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) 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)$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — the number of test cases.

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

Output format:
For each test case, print a single integer — $$$f(n, k)$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 1024.0 MB

Note:
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.

Example input:
4
6 2
4 4
3 1
10 3

Example output:
8
4
6
11

Editorial:
For now, let $$$c(l, r)$$$ denote the number of integer pairs $$$(i, j)$$$ such that $$$l \le i \lt j \le r$$$ (instead of $$$i \le j$$$) and $$$\operatorname{gcd}(i, j) \ge l$$$. So we can add $$$n$$$ to $$$f(n, k)$$$ in the end.
We can construct a straightforward dp where $$$f(n, k) = \min\limits_{i = 1}^{n}{(f(i - 1, k - 1)+c(i, n))}$$$. As a straightforward implementation of $$$c(l, r)$$$ takes $$$\mathcal{O}(n^2 \log_2 n)$$$ time, the total complexity of finding $$$f(n, k)$$$ will be $$$\mathcal{O}(n^5 \log_2 n)$$$ which is quite shameful.
Let's see how to do better.
Tiny Observation: $$$c(x, 2 \cdot x - 1) = 0$$$. It's easy to see why it holds.
Cute Observation: $$$f(n, k) = 0$$$ when $$$k \gt \log_2 n$$$.
Proof: Let $$$L = \log_2 n$$$. Following the tiny observation, we can split the numbers as $$$[1, 1], [2, 3], [4, 7], \ldots, [2^{L - 1}, 2^L - 1], [2^L, n]$$$ without spending a single penny.
Now we can solve $$$f(n, k)$$$ in $$$\mathcal{O}(n^4 \log_2^2 n)$$$ which is still shameful.
So we just have to find $$$f(n, k)$$$ for $$$1 \le n \le 10^5$$$ and $$$1 \le k \le 17$$$.
Let's optimize the calculation for $$$c(l, r)$$$ .
$$$$$$c(l, r) = \sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^{r}{[\gcd(i, j) \ge l]}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}\sum\limits_{i=l}^{r}\sum\limits_{j=i+1}^{r}{[\gcd(i, j) = k]}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}\sum\limits_{i=l, k | i}^{r}\sum\limits_{j=i+1, k | j}^{r}{[\gcd(i, j) = k]}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}\sum\limits_{i=1}^{\left\lfloor \frac{r}{k} \right\rfloor}\sum\limits_{j=i+1}^{\left\lfloor \frac{r}{k} \right\rfloor}{[\gcd(i \cdot k, j \cdot k) = k]}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}\sum\limits_{i=1}^{\left\lfloor \frac{r}{k} \right\rfloor}\sum\limits_{j=i+1}^{\left\lfloor \frac{r}{k} \right\rfloor}{[\gcd(i, j) = 1]}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}\sum\limits_{i=1}^{\left\lfloor \frac{r}{k} \right\rfloor}{\phi(i)}$$$$$$ $$$$$$=\sum\limits_{k=l}^{r}{p(\left\lfloor \frac{r}{k} \right\rfloor)}$$$$$$ Here, $$$p(x) = \sum\limits_{i=1}^{x}{\phi(i)}$$$. We can calculate $$$p(x)$$$ for all $$$x \le n$$$ in $$$\mathcal{O}(n \log_2 n)$$$ and calculate $$$c(l, r)$$$ in $$$\mathcal{O}(n)$$$. So currently we can solve our problem in $$$\mathcal{O}(n^3)$$$ which is still not to be proud of.
But notice that there can be at most $$$2 \sqrt{m}$$$ distinct values in the sequence $$$\left\lfloor \frac{m}{1} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor, \ldots, \left\lfloor \frac{m}{m} \right\rfloor$$$. Check this for a proof. So we can calculate $$$c(l, r)$$$ in $$$\mathcal{O}(\sqrt{n})$$$ which improves our solution to $$$\mathcal{O}(n^2 \sqrt{n})$$$.
But notice that as $$$c(l, r) =\sum\limits_{k=l}^{r}{p(\left\lfloor \frac{r}{k} \right\rfloor)}$$$ we can precalculate the suffix sums for each $$$r=1$$$ to $$$n$$$ over all distinct values of $$$\left\lfloor \frac{r}{k} \right\rfloor$$$ and then calculate $$$c(l, r)$$$ in $$$\mathcal{O}(1)$$$. This preprocessing will take $$$\mathcal{O}(n \sqrt{n})$$$ time and $$$\mathcal{O}(n \sqrt{n})$$$ memory. That means we can solve our problem $$$\mathcal{O}(n^2 + n\sqrt{n})$$$ which is promising.
Critical Observation: $$$c(l, r)$$$ satisfies quadrangle inequality, that is $$$c(i,k)+c(j,l)\le c(i,l)+c(j,k)$$$ for $$$i\le j \le k \le l$$$.
Proof: Let $$$f(i, j, r) =\sum\limits_{k=i}^{j}{p(\left\lfloor \frac{r}{k} \right\rfloor)}$$$. Here, $$$$$$c(i, l) + c(j, k)= f(i, l, l) + f(j, k, k)$$$$$$ $$$$$$= (f(i, j - 1, l) + f(j, l, l)) + (f(i, k, k) - f(i, j - 1, k))$$$$$$ $$$$$$=f(i, j - 1, l) + c(j, l) + c(i, k) - f(i, j - 1, k)$$$$$$ $$$$$$= c(i, k) + c(j, l) + f(i, j - 1, l) - f(i, j - 1, k)$$$$$$ But clearly $$$f(i, j - 1, l) \ge f(i, j - 1, k)$$$ as $$$l \ge k$$$. So $$$c(i,k)+c(j,l)\le c(i,l)+c(j,k)$$$.
You can learn more about quadrangle inequality and how it is useful from here. Read it because I won't describe why it helps us here.
This suggests that we can solve this problem using Divide and Conquer DP or 1D1D DP which will optimize our $$$\mathcal{O}(n^2)$$$ part to $$$\mathcal{O}(n \log_2^2 n)$$$.
To solve for multiple queries we can just precalculate $$$f(n, k)$$$ for $$$1 \le n \le 10^5$$$ and $$$1 \le k \le 17$$$.
Overall complexity: $$$\mathcal{O}(n \log_2^2 n + n\sqrt{n})$$$ where $$$n = 10^5$$$.
This problem can also be solved using Divide and Conquer DP and by calculating $$$c(l, r)$$$ in $$$\mathcal{O}(\sqrt{r-l})$$$ in each level which runs pretty fast in practice (for $$$n = 5 \cdot 10^5$$$, it takes less than 3s) but I don't have a rigorous upper bound on the time complexity. Check out my solution for more clarity.