There is a simple problem like that on Codeforces

With ($$$1 \leq x, y \leq n$$$) then the result will just simply $$$pair(1; n - 1)$$$

When $$$(b\ \text{mod}\ a = 0)$$$ we have $$$(gcd(a, b) = a\ ;\ lcm(a, b) = b)$$$, therefor $$$gcd(a, b) + lcm(a, b) = a + b = n$$$

So if we choose $$$(a, b) = pair(1; n - 1)$$$ then $$$1 + (n - 1) = n$$$ true

But can I find the result in Linear or faster when both $$$x$$$ and $$$y$$$ have to be in range $$$[l, r]$$$ ? Maybe we give $$$pair(-1; -1)$$$ when there is no result

**I found answers in some special cases but not general**

**Input:**

Positive integer $$$n, l, r$$$

**Output:**

Find such $$$pair(x, y)$$$ in $$$range [l, r]$$$ that $$$(gcd(x, y) + lcm(x, y) = n)$$$

**Example 1**

**Example 2**

Notice that $$$\gcd(x, y) | n$$$ since it divides the LHS. You noted that if $$$x | n$$$, then $$$(x, n-x)$$$ works. If $$$n$$$ is prime, by our first statement we know that $$$\gcd(x, y)=1$$$ since it cannot equal $$$n$$$. Thus, we need to find two coprime $$$x, y$$$ s.t. $$$1+xy=n$$$, or equivalently $$$xy=n-1$$$. So if we factor $$$n-1$$$ and find two coprime factors, we can just use those. This should at least get you all queries in $$$O(\sqrt n)$$$ or $$$O(\sigma(n))$$$ if you precompute the divisors of each number using sieve.

There might be a solution that is $$$\log(n)$$$ per query, but nothing I'm seeing right now.

Thanks for the solution.

But what if n is not prime?

If $$$g$$$ $$$=$$$ $$$gcd(x, y)$$$ then $$$lcm(x, y)$$$ $$$=$$$ $$$g \cdot [x / g] \cdot [y / g]$$$ $$$=$$$ $$$g \cdot x_0 \cdot y_0$$$ with $$$gcd(x_0, y_0)$$$ $$$=$$$ $$$1$$$.

For each possible value of $$$g$$$ we need find such pair $$$(x_0, y_0)$$$ that

There are $$$d(n)$$$ possible values of $$$g$$$ that can be limited by $$$O(n^{1/2})$$$ or even $$$O(n^{1/3})$$$. And for each value of $$$g$$$ we need iterate over all divisors of $$$[n / g] - 1$$$, that is $$$O(n^{1/3})$$$ too.

Without some precalculations I don't see any way to solve it faster than $$$O(n^{2/3})$$$ in total.

Actually if there are many queries, for example, and it is possible to precalculate divisors of all numbers $$$\le MAXN$$$, we could store for each number $$$A$$$ only such divisors $$$x$$$ that $$$A = x \cdot y$$$, $$$gcd(x, y) = 1$$$ and for each $$$g$$$ check if there is at least one pair in needed segment in $$$O(log(size))$$$ with binary search. But it will require a lot of memory and time for precalculation (especially if $$$n$$$ is large).

Ah, shoot, I originally thought that OP's idea of just using $$$(x, n-x)$$$ for some $$$x | n$$$ works, but that fails for $$$n=14, l = 4, r = 6$$$. Yes, I think you are correct for the composite $$$n$$$ case.