Solutions to an Equation LightOJ - 1306
一个基础的扩展欧几里得算法的应用。
解方程ax+by=c时，基本就是先记录下a和b的符号fla和flb（a为正则fla为1，为负则fla为-1，flb相同），然后对a和b取绝对值。求出ax+by=gcd(a,b)的一组解x=ansx,y=ansy，那么只有当c是gcd(a,b)的倍数时原方程才可能有解。设g=gcd(a,b)，通解是x=ansx*(c/g)*fla+k*b/g*fla,y=ansy*(c/g)*flb-k*a/g*flb。这里设xa=ansx*(c/g)*fla，xb=b/g*fla，ya=ansy*(c/g)*flb，yb=-(a/g*flb)。
那么这题就是根据通解的式子和x和y的范围去求k的范围，基本操作就是手算一下解不等式。
举例：不等式(x相关)：xa+k*xb>=x1,xa+k*xb<=x2
（解一下就会发现第一个式子解出的是k的最小值还是最大值，与xb的符号有关）
理论上不难，但是符号之类的细节实现起来有难度（...）。另外，a为0或b为0或a、b都为0时都需要特判（...）。
错误记录：
未特判0
upd:
以上应该有错。通解应该是x=ansx*fla+k*(b/g)*fla,y=ansy*flb-k*(a/g)*flb
通解就是那个没错的，但是要注意ansx和ansy是ax+by=gcd(a,b)的解，不是原方程的解。
如果有了一组原方程的解，求通解，那么就不要乘c/g
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL T,x,y,a,b,c,x1,x2,y11,y2,g;
LL gcd(LL a,LL b)
{
LL t;
while(b!=)
{
t=a;
a=b;
b=t%b;
}
return a;
}
LL exgcd(LL a,LL b,LL& x,LL& y)
{
if(b==)
{
x=;
y=;
return a;
}
else
{
LL t=exgcd(b,a%b,x,y);
LL t1=x;
x=y;
y=t1-a/b*y;
return t;
}
}
int main()
{
LL TT,fla,flb,xa,xb,ya,yb,kl,kr,kl1,kr1;
scanf("%lld",&T);
for(TT=;TT<=T;TT++)
{
scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x1,&x2,&y11,&y2);
c=-c;
if(a==&&b==)
{
if(c==)
{
printf("Case %lld: %lld\n",TT,max(0ll,(x2-x1+)*(y2-y11+)));
}
else
{
printf("Case %lld: %lld\n",TT,0ll);
}
continue;
}
if(a==)
{
if(c%b==&&(c/b>=y11)&&(c/b<=y2))
printf("Case %lld: %lld\n",TT,x2-x1+);
else
printf("Case %lld: %lld\n",TT,0ll);
continue;
}
if(b==)
{
if(c%a==&&(c/a>=x1)&&(c/a<=x2))
printf("Case %lld: %lld\n",TT,y2-y11+);
else
printf("Case %lld: %lld\n",TT,0ll);
continue;
}
fla=;flb=;
if(a<)
{
a=-a;
fla=-;
}
if(b<)
{
b=-b;
flb=-;
}
g=gcd(a,b);
if(c%g!=)
{
printf("Case %lld: %lld\n",TT,0ll);
continue;
}
exgcd(a,b,x,y);
xa=x*(c/g)*fla;
xb=b/g*fla;
ya=y*(c/g)*flb;
yb=-(a/g*flb);
//x=xa+k*xb,y=ya+k*yb
if(xb>)
{
kl=ceil((double)(x1-xa)/xb);
kr=floor((double)(x2-xa)/xb);
}
else
{
kr=floor((double)(x1-xa)/xb);
kl=ceil((double)(x2-xa)/xb);
}
if(yb>)
{
kl1=ceil((double)(y11-ya)/yb);
kr1=floor((double)(y2-ya)/yb);
}
else
{
kr1=floor((double)(y11-ya)/yb);
kl1=ceil((double)(y2-ya)/yb);
}
//if(kl1>kr1) swap(kl1,kr1);
printf("Case %lld: %lld\n",TT,max(min(kr1,kr)-max(kl1,kl)+,0ll));
}
return ;
}