How to do this modified Bezout's Theorem thingy?
Difference between en2 and en3, changed 291 character(s)
I'm trying to solve this problem: [Xum](https://codeforces.net/problemset/problem/1427/E)↵

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 [user:Thalleous,2024-08-20] and [user:_inferno_,2024-08-20] 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](https://codeforces.net/contest/1427/submission/277308913)**

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Red0 2024-08-20 15:49:56 291
en2 English Red0 2024-08-18 10:48:53 157
en1 English Red0 2024-08-18 10:43:04 694 Initial revision (published)