Quotient and Remainder

Let a quotient value be $q$ and a remainder value be $r$. We need to know whether they can be paired by some operation.

The operation asks for integers $x,y$ such that:

• $1 \le y < x \le k$,
• $\left\lfloor \frac{x}{y}\right\rfloor=q$,
• $x \bmod y=r$.

By quotient-remainder decomposition, this means

$x = qy + r$

with

$0 \le r < y.$

Here every $r_i$ is positive, so $r\ge 1$. That already gives $y>x$? Nope, careful: it gives $y>r$. The smallest divisor that could possibly work is therefore

$y=r+1.$

For fixed $q$ and $r$, increasing $y$ only increases $x=qy+r$, because $q\ge 1$. So if the smallest valid $y$ does not fit under $k$, nothing else will. The pair works exactly when

$q(r+1)+r \le k.$

Expand it:

$qr+q+r\le k$

$r(q+1)+q\le k$

So for a fixed quotient $q$, the largest remainder it can accept is

$L(q)=\left\lfloor\frac{k-q}{q+1}\right\rfloor.$

If some remainder $r\le L(q)$, then choose $y=r+1$ and $x=q(r+1)+r$. Done. If $r>L(q)$, no valid $y$ exists. That's the whole math part. The rest is matching without doing something hilariously overkill like full bipartite matching.

Turning the problem into matching

Each quotient value $q_i$ becomes one limit:

$L_i = \left\lfloor\frac{k-q_i}{q_i+1}\right\rfloor.$

That quotient can match any remainder $r_j$ with

$r_j \le L_i.$

So every quotient has a simple prefix of acceptable remainders: all small enough values. This structure is greedy-friendly.

Sort all limits $L_i$ in increasing order. Sort all remainders $r_j$ in increasing order.

Then scan the limits from smallest to largest, keeping a pointer to the smallest unused remainder.

For the current limit $L$:

• If the smallest unused remainder is $\le L$, match it with this quotient.
• Otherwise, this quotient cannot match anything, because every other unused remainder is even larger. Skip it.

This is not vibes-based greedy. It is forced.

If the smallest available remainder does not fit into the current smallest limit, then no available remainder fits that limit. So skipping that quotient loses nothing.

If it does fit, matching it is always safe: using the smallest remainder is the least demanding choice, leaving larger remainders for larger future limits. Giving this easy remainder to a later, more flexible quotient would be pointless nonsense.

Algorithm

For each test case:

1. Read $q$ and $r$.
2. Replace each $q_i$ by $L_i=\left\lfloor\frac{k-q_i}{q_i+1}\right\rfloor$.
3. Sort the limits.
4. Sort the remainders.
5. Greedily match with two pointers.

Correctness proof

We prove the algorithm outputs the maximum number of operations.

First, for any quotient $q$ and remainder $r$, they can be used in one operation iff $r\le L(q)$.

If an operation exists, then $x=qy+r$ and $r<y$. Since $y\ge r+1$, we have

$x=qy+r\ge q(r+1)+r.$

Because $x\le k$, it follows that $q(r+1)+r\le k$, which is equivalent to $r\le L(q)$.

Conversely, if $r\le L(q)$, choose $y=r+1$ and $x=q(r+1)+r$. Then $r<y$, $x\le k$, and $x=qy+r$, so the quotient is $q$ and the remainder is $r$. Thus the pair is valid.

So the original problem is exactly: match each limit $L_i$ with at most one remainder $r_j$ such that $r_j\le L_i$.

Now sort limits and remainders increasingly. Consider the greedy scan.

When processing a limit $L$, let $r$ be the smallest unused remainder.

If $r>L$, then every unused remainder is also greater than $L$, so this limit cannot be matched in any valid solution using the remaining remainders. Skipping it is forced.

If $r\le L$, greedy matches them. Take any optimal solution for the remaining items plus this limit. If this optimal solution does not match $L$ to $r$, then either $r$ is unused, or $r$ is matched to some later limit $L'\ge L$. In both cases, we can match $L$ to $r$ instead. This does not reduce the number of matches, because $r$ fits $L$, and later limits are at least as flexible as $L$. Therefore there exists an optimal solution that includes the greedy match.

By repeating this argument for every processed limit, every greedy decision is compatible with some optimal solution. Hence the greedy algorithm is optimal.

Complexity

Sorting dominates:

$O(n\log n)$

per test case, with total $n\le 2\cdot 10^5$, so this easily fits. Memory usage is $O(n)$.

Use long long, because $k$ is up to $10^{18}$. The products are still safe in signed 64-bit here, but computing the limit directly as $(k-q)/(q+1)$ is cleaner anyway.