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.