### SPyofgame's blog

By SPyofgame, history, 4 weeks ago, ,

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

• +5

 » 4 weeks ago, # | ← Rev. 2 →   +17 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.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for the solution.
•  » » 4 weeks ago, # ^ |   +9 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 $ceil(l / g) \le x_0, y_0 \le floor(r / g)$ $gcd(x_0, y_0)$ $=$ $1$ $1 + x_0 \cdot y_0$ $=$ $[n / g]$ <=> $x_0 \cdot y_0$ $=$ $[n / g] - 1$ 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).
•  » » » 4 weeks ago, # ^ |   0 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.