SPyofgame's blog

By SPyofgame, history, 4 weeks ago, In English,

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
 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    Thanks for the solution.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.