How to do this modified Bezout's Theorem thingy?

Правка en3, от Red0, 2024-08-20 15:49:56

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

Теги math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Red0 2024-08-20 15:49:56 291
en2 Английский Red0 2024-08-18 10:48:53 157
en1 Английский Red0 2024-08-18 10:43:04 694 Initial revision (published)