/* Extend GCD and Linear congruence equation with 2 unkonwns. * ax + by = c, has solutions iff c | gcd(a,b) * use eGCD to get ax' + by' = gcd(a,b) * x0=x'*c/gcd(a,b) * y0=y'*c/gcd(a,b) * solution is : x = x0 + b/gcd(a,b) * t * y = y0 - a/gcd(a,b) * t * for any int t */ #include<cstdio> #include<cstring> #include<cmath> typedef __int64 LL; LL egcd(LL a, LL b, LL &x, LL &y) { if(b==0) { x=1; y=0; return a; } else { LL ans = egcd(b,a%b,x,y); LL tx=x,ty=y; x=ty; y=tx-(a/b)*ty; return ans; } } LL abs(LL x) { return x>0?x:-x; } LL sign(LL x) { if(x>0) return 1; else if(x<0) return -1; return 0; } LL max(LL a, LL b) { return a>b?a:b; } LL min(LL a, LL b) { return a<b?a:b; } int main() { LL a,b,c,x1,x2,y1,y2; LL xL,xR,yL,yR,dx,dy,g,x0,y0; LL tl,tr,pl,pr,inc; while(scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d",&a,&b,&c,&x1,&x2,&y1,&y2)!=EOF) { if(a==0&&b==0) { if(c) printf("0\n"); else printf("%I64d\n",(x2-x1+1)*(y2-y1+1)); } else if(a==0&&b!=0) { if(c%b) printf("0\n"); else if(c!=0) printf("%I64d\n",(x2-x1+1)); else printf("%d\n",((x1<=0)&&(x2>=0))?1:0); } else if(a!=0&&b==0) { if(c%a) printf("0\n"); else if(c!=0) printf("%I64d\n",(y2-y1+1)); else printf("%d\n",((y1<=0)&&(y2>=0))?1:0); } else { g=egcd(a,b,x0,y0); inc=-sign(a)*sign(b); if(-c%g) printf("0\n"); else { x0*=(-c/g); y0*=(-c/g); //printf("%I64d*%I64d + %I64d*%I64d = %I64d\n",a,x0,b,y0,-c); dx=b/g; dy=-a/g; if((x1-x0)%dx) { double tt=(x1-x0)/((double) dx); LL ttl=(LL)floor(tt); if(x0+dx*ttl>=x1) tl=ttl; LL ttr=(LL)ceil(tt); if(x0+dx*ttr>=x1) tl=ttr; } else { tl=(x1-x0)/dx; } if((x2-x0)%dx) { double tt=(x2-x0)/((double) dx); LL ttl=(LL)floor(tt); if(x0+dx*ttl<=x2) tr=ttl; LL ttr=(LL)ceil(tt); if(x0+dx*ttr<=x2) tr=ttr; } else tr=(x2-x0)/dx; if((y1-y0)%dy) { double tt=(y1-y0)/((double) dy); LL ttl=(LL)floor(tt); if(y0+dy*ttl>=y1) pl=ttl; LL ttr=(LL)ceil(tt); if(y0+dy*ttr>=y1) pl=ttr; } else { pl=(y1-y0)/dy; } if((y2-y0)%dy) { double tt=(y2-y0)/((double) dy); LL ttl=(LL)floor(tt); if(y0+dy*ttl<=y2) pr=ttl; LL ttr=(LL)ceil(tt); if(y0+dy*ttr<=y2) pr=ttr; } else pr=(y2-y0)/dy; if(inc>0) { if(y1>y0+tl*dy) { tl=pl; } if(y2<y0+tr*dy) { tr=pr; } } else { if(y1>y0+tr*dy) { tr=pl; } if(y2<y0+tl*dy) { tl=pr; } } //printf("%I64d %I64d\n",dx,dy); //printf("%I64d %I64d %I64d %I64d\n",tl,tr,pl,pr); printf("%I64d\n",max(tr,tl)-min(tr,tl)+1); } } } return 0; } |