Red0's blog

How to do this modified Bezout's Theorem thingy?
By Red0, history, 4 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 _inferno_ 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

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

            oh wait wait wait, good point. Thanks!

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

            How to be that good at math

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

          simply take the entire equation modulo x

          → Reply
          • »
            »
            »
            »
            »
            »
            4 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
          • »
            »
            »
            »
            »
            »
            4 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
      • »
        »
        »
        »
        4 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply