I'm trying to solve this problem: [Xum](https://mirror.codeforces.com/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://mirror.codeforces.com/contest/1427/submission/277308913)**
↵
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://mirror.codeforces.com/contest/1427/submission/277308913)**
