devarshi09's blog

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years 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.

»
8 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.

»
8 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?

»
6 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

»
4 months 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

»
6 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

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;

}