devarshi09's blog

By devarshi09, history, 2 years ago,

I am not able to solve problem "once upon a time" from this(http://codeforces.com/gym/100963/attachments) set . I tried extended euclidean algorithm. Can anyone provide the solution (in form of code or editorial) for this problem Or help me debug my code (http://codeforces.com/gym/100963/attachments) .

• 0

 » 2 years ago, # |   0 Auto comment: topic has been updated by Devarshi (previous revision, new revision, compare).
 » 22 months ago, # | ← Rev. 2 →   0 https://cp-algorithms.com/algebra/linear-diophantine-equation.htmlJust modify the find_all_solutions function.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Exactly where is that function present?
 » 5 months ago, # | ← Rev. 2 →   -6 Same here. Here's what I have: Lets say $y$ is the answer. $y \equiv n \mod m$ and $y \equiv k \mod a$. So we have to find $x$ such that $n + xm \equiv k \mod a$. The answer would be $n + xm$. This is a Diophantine equation of the form $xm - ax' = k - n$.I'm also trying to find the smallest $y$ such that $y >= max(n, k+a)$. I do that by generating new solutions for the Diophantine equation.Now, I don't know what happens when $a = 0$ or $m = 0$. I suppose I have to print $\textit{Impossible}$ here but I can't get the AC yet. Same thing for $n = 0$ or $k = 0$. A little help here would be nice.
 » 5 months ago, # |   0 I'm also unable to solve this problem and cant find an editorial on this anywhere.Can someone who solved this please post the solution?
 » 3 months ago, # |   0 please help me with this question i am unable to understand how extended gcd algorithm will help me
 » 6 weeks ago, # |   0 Hey did you solve this? Because I am unable to solve it by extended euclidean algorithm or by any other means