### devarshi09's blog

By devarshi09, history, 5 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

| Write comment?
 » 5 years ago, # |   0 Auto comment: topic has been updated by devarshi09 (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   0 https://cp-algorithms.com/algebra/linear-diophantine-equation.htmlJust modify the find_all_solutions function.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Exactly where is that function present?
 » 3 years 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?
»
2 years 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;

}

•  » » 2 years ago, # ^ |   0 in ss when you increase the value of x should you not decrease the value of y?
•  » » » 2 years ago, # ^ |   0 no, because initially he had multiplied "y" with a -1.so the factor by which we change x and y are now of the same sign.
•  » » » » 2 years ago, # ^ |   0 Thank you man ...got it
 » 17 months ago, # | ← Rev. 2 →   +8 I just solved this problem, here is my solution. #include using namespace std; using ll = long long; const char nl = '\n'; /* returns the gcd(a, b) and at the same time, solves the linear combination: a*x + b*y = gcd(a, b) for integers x, y. */ ll extgcd(ll a, ll b, ll& x, ll& y) { x = 1, y = 0; ll x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { ll q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1; } int main() { cin.tie(0); ios::sync_with_stdio(0); ll n, m, a, k, xg, yg, x0, y0, g, c, shift; while(true) { cin >> n >> m >> a >> k; if(n == 0 && m == 0 && a == 0 && k == 0) return 0; // because the man can only reach for the first time at k + a k += a; // this ensures a situation where the man starts after the woman if(k < n) { swap(n, k), swap(m, a); } // check for solution to diophantine equation g = extgcd(a, m, xg, yg);// yields: a*xg + m*yg = gcd(a, m) c = k - n; if(c % g != 0) { cout << "Impossible\n"; continue; } // now: a*x0 + m*y0 = c x0 = xg * c / g, y0 = yg * c / g; // shift x0 so that |x0| is at a minimum and x0 < 0 // equivalently, shifting y0 so that |y0| is at a minimum and y0 > 0 if(x0 > 0) { shift = (x0 * g + m - 1) / m; x0 -= shift * m / g; y0 += shift * a / g; } else { shift = (-x0 * g) / m; x0 += shift * m / g; y0 -= shift * a / g; } assert(k - x0 * a == n + y0 * m); cout << n + y0 * m << nl; } } 
 » 14 months ago, # | ← Rev. 5 →   +5 I know that this is a very old post, but i would like to help other people like me that also want to better understand the solution to this problem.To simple began the solution, its good to observe that we want to find x and y with some constraints that solve this equation :$k+a*x=n+m*y$$x \geq 1, x \in Z$$y \geq 0, y \in Z$x must be greater or equal than 1 because when x equals to 0, the man approaches and not stretches, and x < 0 does not make sense.y must be greater or equal than 0 because when y equals to 0, the woman already stretches, and y < 0 does not make sense.Also observe that we can write the above equation in another way:$a*x-m*y=n-k$And also:$a*x+(-m)*y=n-k$And this type of equation can be solved simply using the extend euclidean algorithm, see the link.Observe that we don't have answer if n-k is not a multiple of $gcd(a,-m)$.Unfortunately, sometimes x, and y could be negative, but observe that:$0 = a*\frac{-m}{gcd(a,-m)}+(-m)*\frac{a}{gcd(a,-m)}$And use that to change x and y without affect the answer.See my code below #include using namespace std; typedef long long ll; ll gcd(ll a, ll b, ll* x, ll* y){ if(b == 0){ *x = 1; *y = 0; return a; } ll x1, y1; ll g = gcd(b, a%b, &x1, &y1); *x = y1; *y = x1-y1*(a/b); return g; } int main(){ while(1){ ll n, m, a, k; cin >> n >> m >> a >> k; if(n==0 && m==0 && a==0 && k==0){ break; } ll x, y; ll g = gcd(a, -m, &x, &y); ll dif = n-k; if(dif%g!=0){ cout << "Impossible\n"; continue; } if(g < 0){ x = -x, y = -y, g = -g; } x = x*(dif/g); y = y*(dif/g); ll d = m/g; if(x <= 0){ ll mult = (abs(x)/d)+1; x += d*mult; }else{ ll mult = (x-1)/d; x -= d*mult; } cout << k+a*x << endl; } return 0; } 
•  » » 11 months ago, # ^ |   0 Sr but can I don't know why do we have : ll d = m/g; and then how we find x by: if(x <= 0){ ll mult = (abs(x)/d)+1; x += d*mult; }else{ ll mult = (x-1)/d; x -= d*mult; } Can you explain more, thank you so much
•  » » » 3 weeks ago, # ^ |   0 i am having same problem can u help me out
 » 8 months ago, # | ← Rev. 2 →   0 I am getting WA on test case 2 Can someone help me in which case my code is getting wrong My Approach: get initial solutions to equation mx+ay=k+a-n and then shift the solutions using x'=x+kg/a and y=y-kg/m to get both x and y greater than zerocode: 174696154