SGU 106 – extend GCD & Linear Congruence Equation

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

Leave a Reply

Your email address will not be published.