bricked_'s blog

How to do this modified Bezout's Theorem thingy?
By bricked_, history, 6 months 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.

Update: Thanks a lot to Thalleous and bricked. for their help! Please feel free to try and solve this if you haven't yet, and here is my submission if you want to check it out! 277308913

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
6 months 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
  • »
    »
    6 months 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
    • »
      »
      »
      6 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 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
      • »
        »
        »
        »
        6 months 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
        • »
          »
          »
          »
          »
          6 months 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
          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            oh wait wait wait, good point. Thanks!

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

            How to be that good at math

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

        Oh wait sorry to bother you my friend, but could you please explain why we are able to deduce $$$by ≡ -1$$$ $$$(mod$$$ $$$x)$$$ from your first equation? Thanks!

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

          simply take the entire equation modulo x

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

            ohh so we are able to cancel out ax. i see thanks!

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

            edit: mb, didn't realize meaning of 3 horizontal lines.

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

        Also just to clarify, in your extended_euclidean method, is it something like this?

        int extended_euclidean(int a, int b, int &inv, int &rem) {
    if(b == 0) {
        inv = 1;
        rem = 0;
        return a;
    }
    
    int x1, y1;
    int d = extended_euclidean(b, a%b, x1, y1);
    inv = y1;
    rem = x1-y1*(a/b);
    return d;
}

        I'm just wondering, because I believe I've done everything in the way you've taught me, however I appear to be getting WA on testcase 2 as shown here: 277250662

        EDIT: I have solved. The error was a lack of my understanding in the extended euclidean algorithm :). It's a%b, and we want y%x, so just swapping the order of x and y and slight modification leads to AC. New submission: 277308913

        → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by bricked_ (previous revision, new revision, compare).

→ Reply