### 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 devarshi09 (previous revision, new revision, compare).
 » 2 years ago, # | ← Rev. 2 →   0 https://cp-algorithms.com/algebra/linear-diophantine-equation.htmlJust modify the find_all_solutions function.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Exactly where is that function present?
 » 8 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.
 » 8 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?
 » 6 months ago, # |   0 please help me with this question i am unable to understand how extended gcd algorithm will help me
 » 4 months ago, # |   0 Hey did you solve this? Because I am unable to solve it by extended euclidean algorithm or by any other means
»
6 weeks ago, # |
-6

# include<bits/stdc++.h>

using namespace std;

# 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; }

ll x1,y1,g;

g=gcd(b,a%b,x1,y1);

x=y1;
y=x1-((a/b)*y1);

return g;

}

bool anys(ll a, ll b, ll& x, ll &y, ll c,ll& g) { g=gcd(a,b,x,y);

if(c%g)
return false;

x*=(c/g);
y*=(c/g)*(-1);

return true;

}

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;

if(!anys(a,b,x,y,c,g))
return false;

a/=g;
b/=g;

if(b>0)
{
ss(a,b,x,y,(0-x)/b);

if(x<0)
{
x+=b;
y+=a;
}
}

if(a>0  && y<0)
{
ss(a,b,x,y,(0-y)/a);

if(y<0)
{
x+=b;
y+=a;
}

}

if(x<0 || y<0)
return false;

else return true;

}

int main() {

FastIO

while(1)
{
ll n,m,a,k,c,x,y;
cin>>n>>m>>a>>k;

if(n+m+k+a==0)
break;

c=k+a-n;

if(c==0)
cout<<n<<nl;

else if(a==0 && m==0)
cout<<"Impossible"<<nl;

else
{
bool flag=alls(m,a,x,y,c);

if(flag)
cout<<(m*x)+n<<nl;

else cout<<"Impossible"<<nl;
}

}

return 0;

}