Can somebody help me with solving one codeforces problem. Link of problem is http://codeforces.com/problemsets/acmsguru/problem/99999/106 . I got WA 13.
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;
return 0;
}
else if(a==0 && b==0 && c==0)
{
ll l=max(minx,miny);
ll r=min(maxx,maxy);
if(l>r)
cout<<0;
else
cout<<r-l+1;
return 0;
}
else if(a==0 && b!=0 && c%b==0 && c/b>=miny && c/b<=maxy)
{
cout<<maxx-minx+1;
return 0;
}
else if(a!=0 && b==0 && c%a==0 && c/a>=minx && c/a<=maxx)
{
cout<<maxy-miny+1;
return 0;
}
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);
//db(g);
if(lx==-1 && rx==-1)
cout<<0;
else
cout<<(rx-lx)*g/b+1;
return 0;
}