Codeforces ACMSGURU-106

editorial
,
1

Link of problem:

Can anyone hel me? I got WA 20. I used linear Diophantine equation and extended Euclidian algorithms from cp-algorithms.com, but I got WA. These are links that I used:

  1. Extended Euclidean Algorithm - Algorithms for Competitive Programming
  2. Linear Diophantine Equations - Algorithms for Competitive Programming

My code is :

#include <bits/stdc++.h>
#define PII pair<ll,ll>
#define db(x) cerr<<#x<<“=”<<x<<endl
typedef long long ll;

using namespace std;

ll gcd(ll a,ll b,ll &x,ll &y)
{
if(a==0)
{
x=0;
y=1;
return b;
}
ll x1,y1;
ll d=gcd(b%a,a,x1,y1);
x=y1-(b/a)*x1;
y=x1;
return d;
}

bool find_any_solution(ll a,ll b,ll c,ll &x0,ll &y0,ll &g)
{
g=gcd(abs(a),abs(b),x0,y0);
if(c%g)
return false;
x0*=c/g;
y0*=c/g;
if(a<0)
x0=-x0;
if(b<0)
y0=-y0;
return true;
}

void shift_solution(ll &x,ll &y,ll a,ll b,ll cnt)
{
x+=cntb;
y-=cnta;
}

PII find_all_solution(ll a,ll b,ll c,ll minx,ll maxx,ll miny,ll maxy)
{
ll x,y,g;
PII res= {-1,-1};
if(!find_any_solution(a,b,c,x,y,g))
return res;
a/=g;
b/=g;

ll sign_a=(a>0)?+1:-1;
ll sign_b=(b>0)?+1:-1;

shift_solution(x,y,a,b,(minx-x)/b);
if(x<minx)
    shift_solution(x,y,a,b,sign_b);
if(x>maxx)
    return res;
ll lx1=x;

shift_solution(x,y,a,b,(maxx-x)/b);
if(x>maxx)
    shift_solution(x,y,a,b,-sign_b);
ll rx1=x;

shift_solution(x,y,a,b,-(miny-y)/a);
if(y<miny)
    shift_solution(x,y,a,b,-sign_a);
if(y>maxy)
    return res;
ll lx2=x;

shift_solution(x,y,a,b,-(maxy-y)/a);
if(y>maxy)
    shift_solution(x,y,a,b,sign_a);
ll rx2=x;

if(lx2>rx2)
    swap(lx2,rx2);

ll lx=max(lx1,lx2);
ll rx=min(rx1,rx2);

if(lx>rx)
    return res;
res.first=lx;
res.second=rx;
return res;

}

int main()
{
ll a,b,c,minx,maxx,miny,maxy;
cin>>a>>b>>c>>minx>>maxx>>miny>>maxy;
c=-c;
if(a==0 && b==0 && c!=0)
{
cout<<0;
}
else if(a==0 && b==0 && c==0)
{
cout<<(maxx-minx+1)*(maxy-miny+1);
}
else if(a==0 && b!=0 && c%b==0 && c/b>=miny && c/b<=maxy)
{
cout<<maxx-minx+1;
}
else if(a!=0 && b==0 && c%a==0 && c/a>=minx && c/a<=maxx)
{
cout<<maxy-miny+1;
}
else
{
PII ind=find_all_solution(a,b,c,minx,maxx,miny,maxy);
ll lx=ind.first;
ll rx=ind.second;
ll g=__gcd(a,b);
if(lx==-1 && rx==-1)
cout<<0;
else
cout<<(rx-lx)*g/b+1;
}

return 0;

}

Can you show my mistake or hint to solve this problem easily? Thank you in advance.