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) .
Auto comment: topic has been updated by devarshi09 (previous revision, new revision, compare).
https://cp-algorithms.com/algebra/linear-diophantine-equation.html
Just modify the find_all_solutions function.
Exactly where is that function present?
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.
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?
please help me with this question i am unable to understand how extended gcd algorithm will help me
Hey did you solve this? Because I am unable to solve it by extended euclidean algorithm or by any other means
include<bits/stdc++.h>
using namespace std;
define FastIO ios_base::sync_with_stdio(false); cin.tie(0);
define ll long long
define ull unsigned long long
define pb push_back
define All(x) (x).begin(),(x).end()
define mp make_pair
define nl "\n"
typedef pair<int,int>ii; typedef vectorvi; typedef vectorvii; typedef vectorvvi; typedef vectorvl; typedef vector vvl; template void print(T& a) { for(auto x:a) cout<<x<<" "; cout<<"\n"; }
ll gcd(ll a, ll b, ll& x, ll& y) { if(b==0) { x=1; y=0; return a; }
}
bool anys(ll a, ll b, ll& x, ll &y, ll c,ll& g) { g=gcd(a,b,x,y);
}
void ss(ll a, ll b, ll& x, ll& y,ll cnt) { x+=(cnt*b); y+=(cnt*a); }
bool alls(ll a, ll b, ll& x, ll& y, ll c) { ll cnt,g;
}
int main() {
}