Red0's blog

How to do this modified Bezout's Theorem thingy?
By Red0, history, 3 hours ago, In English

I'm trying to solve this problem: Xum

And it's hard enough that I look at the editorial.

Then I meet this Bezout's Theorem for the first time ever in my life, which online, it states that there exist $$$a$$$ and $$$b$$$ for any equation in the form of $$$ax+by=gcd(x, y)$$$, or in the case of this problem where both $$$x$$$ and $$$y$$$ are relatively prime, $$$ax+by=1$$$.

This is a classic Diophantine equation, which can be solved using the Extended Euclidean Algorithm. However what the problem asks us for is to find values of $$$a$$$ and $$$b$$$ such that $$$a,b ≥ 0$$$ and $$$ax-by=1$$$. How do we do this?

Thanks!

If you are like me and missed some tiny important details when reading, it might help to know beforehand that $$$x ≤ 999,999$$$ and is odd for all testcases.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
2 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

So you are given with x, y and your task is to find all possible pairs of (a,b) so that ax — by = 1 right?

→ Reply
  • »
    »
    2 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Nah, just one pair of non-negative a, b such that ax-by = 1. It would probably be helpful for you to read the problem asw, as we are only given x, and we need to find y(which I've done).

    → Reply
    • »
      »
      »
      2 hours ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      Then this will be an easy task. Let me write out the original equation

      $$$ ax-by=1 \rightarrow ax = by + 1 \rightarrow a = \frac{by+1}{x} \rightarrow by \equiv -1\ (mod\ x) $$$

      After that, you will compute the Modular Inverse of $$$y$$$ mod $$$x$$$ since $$$gcd(x,y)=1$$$ so it is possible to find the inverse $$$y^{-1}$$$

      $$$ y \times y^{-1} \equiv 1\ (mod\ x) $$$

      Once $$$y^{-1}$$$ is found, you can calculate b as:

      $$$ b \equiv-y^{-1}\ (mod\ x) $$$

      This can be express to:

      $$$ b \equiv x - y^{-1}\ (mod\ x) $$$

      So here is the code about the way to calculate the inverse modular:

      ll modInverse(ll y, ll x) {
    ll inv, r;
    ll g = extended_euclidean(y, x, inv, r);
    if (g != 1) {
        cout << "Inverse doesn't exist";
        return -1;
    } else {
        inv = (inv % x + x) % x;
        return inv;
    }
}

      Then

      ll inv = modInverse(y, x);
if (inv != -1) {
    ll b = (x - inv) % x;
    return b;
}

      After calculating $$$b$$$ you can substitute in and calculate $$$a$$$

      $$$ a = \frac{by+1}{x} $$$
      → Reply
      • »
        »
        »
        »
        109 minutes ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Um, we're only allowed to use '+' and xor operations as stated in the problem :)

        → Reply
        • »
          »
          »
          »
          »
          88 minutes ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But you are required to find $$$a$$$ and $$$b$$$ after finding $$$a$$$ and $$$b$$$.Then after that if $$$b$$$ is odd you can add $$$y$$$ to $$$a$$$ to have $$$(a+y)$$$ on the board and add $$$x$$$ to $$$b$$$ to have $$$(b+x)$$$ on the board (in order to make $$$b' = b+x$$$ even).

          If $$$b$$$ is even and you have ($$$x$$$, $$$y$$$, $$$a$$$, $$$b$$$) you will use '+' to have $$$ax$$$ in $$$O(log(a))$$$ and $$$by$$$ in $$$O(log(b))$$$. If $$$b$$$ is odd and you have ($$$x$$$, $$$y$$$, $$$(a+y)$$$, $$$(b+x)$$$) you will also use '+' to have $$$x(a+y)$$$ in $$$O(log(a+y))$$$ and $$$y(b+x)$$$ in $$$O(log(b+x))$$$

          After having $$$ax$$$ and $$$by$$$ and since $$$ax-by=1$$$ you can use '^' to have ax^by=1. Or after having $$$x(a+y)$$$ ad $$$y(b+x)$$$ and since $$$x(a+y)-y(b+x)=1$$$ you can use '^' to have $$$(x(a+y))$$$ ^ $$$(y(b+x)) = 1$$$

          → Reply
          • »
            »
            »
            »
            »
            »
            85 minutes ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            oh wait wait wait, good point. Thanks!

            → Reply