devarshi09's blog

Problem : Once upon a time problem
By devarshi09, history, 2 years ago, In English

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) .

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Devarshi (previous revision, new revision, compare).

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://cp-algorithms.com/algebra/linear-diophantine-equation.html

Just modify the find_all_solutions function.

→ Reply
»
5 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

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.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me with this question i am unable to understand how extended gcd algorithm will help me

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey did you solve this? Because I am unable to solve it by extended euclidean algorithm or by any other means

→ Reply