SGU 106 The Equation 扩展欧几里得应用

Sol：线性不定方程+不等式求解

证明的去搜下别人的证明就好了。。。数学题。

#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
	if(a==0&&b==0) return -1;
	if(b==0){x=1;y=0;return a;}
	long long d=extend_gcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

long long a,b,c,x1,x2,y1,y2,ans;

int main()
{
	cin>>a>>b>>c>>x1>>x2>>y1>>y2;
	c=-c;
	if(a==0&&b==0)
	{
		if(c==0)  ans=(x2-x1+1)*(y2-y1+1);
	}
	else if(a==0)
	{
		if(c%b==0&&c/b>=y1&&c/b<=y2)
			ans=x2-x1+1;
	}
	else if(b==0)
	{
		if(c%a==0&&c/a>=x1&&c/a<=x2)
			ans=y2-y1+1;
	}
	else
	{
		long long x=0,y=0;
		long long d=extend_gcd(a,b,x,y);
		if(c%d==0)
		{
			long long X=x*(c/d);
			long long Y=y*(c/d);
			long long k1,k2,k3,k4;
			if(x1<=X||(x1-X)*d%b==0)
				k1=(x1-X)*d/b;
			else
				k1=(x1-X)*d/b+1;
			if(x2>=X||(X-x2)*d%b==0)
				k2=(x2-X)*d/b;
			else
				k2=(x2-X)*d/b-1;
			if(y1<=Y||(y1-Y)*d%a==0)
				k3=(Y-y1)*d/a;
			else
				k3=(Y-y1)*d/a-1;
			if(y2>=Y||(Y-y2)*d%a==0)
				k4=(Y-y2)*d/a;
			else
				k4=(Y-y2)*d/a+1;
			if(k1>k2) swap(k1,k2);
			if(k3>k4) swap(k3,k4);
			ans=min(k2,k4)-max(k1,k3)+1;
		}
	}
	printf("%I64d
",ans);
	return 0;
}