1213 解的个数
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
已知整数x,y满足如下面的条件:
ax+by+c=0
p<=x<=q
r<=y<=s
求满足这些条件的x,y的个数。
输入描述 Input Description
第一行有一个整数n（n<=10），表示有n个任务。n<=10
以下有n行，每行有7个整数，分别为：a,b,c,p,q,r,s。均不超过108。
输出描述 Output Description
共n行，第i行是第i个任务的解的个数。
样例输入 Sample Input
2
2 3 -7 0 10 0 10
1 1 1 -10 10 -9 9
样例输出 Sample Output
1
19
数据范围及提示 Data Size & Hint
分类标签 Tags
欧几里德定理 数论
/*
裸的扩展欧几里得问题.
不过要特判一次函数的情况.
W到挺(如图).
呵呵了..
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
LL n,a,b,c,lx,rx,ly,ry,x,y,a1,b1;
LL ans;
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*f;
}
void ex_gcd(LL a,LL b,LL &x,LL &y)
{
if(!b){x=1,y=0;return ;}
else ex_gcd(b,a%b,y,x),y-=x*(a/b);
}
void slove()
{
int g=__gcd(a,b);
c*=-1;
if(!a&&!b)
{
if(c||lx>rx||ly>ry) printf("0
");
else cout<<(rx-lx+1)*(ry-ly+1)<<endl;
return ;
}
if(!a)
{
y=c/b;
if(ly<=y&&y<=ry&&!(c%b)) printf("1
");
else printf("0
");
return ;
}
if(!b)
{
x=c/a;
if(lx<=x&&x<=rx&&!(c%a)) printf("1
");
else printf("0
");
return ;
}
if(c%g)
{
printf("0
");return ;
}
x=y=0;ans=0;
ex_gcd(a,b,x,y);
x=x*c/g,y=y*c/g;
a=a/g,b=b/g;
int t=0;
if(x<lx)
{
while(x+t*b<lx) t++;
while(x+t*b<rx)
{
if(ly<=y-t*a&&y-t*a<=ry) ans++;
t++;
}
}
else if(x>rx)
{
while(x-t*b>rx) t++;
while(x-t*b>lx)
{
if(ly<=y+t*a&&y+t*a<=ry) ans++;
t++;
}
}
else if(x>=lx&&x<=rx)
{
while(x+t*b<=rx)
{
if(ly<=y-t*a&&y-t*a<=ry) ans++;
t++;
}
t=-1;
while(x+t*b>=lx)
{
if(ly<=y-t*a&&y-t*a<=ry) ans++;
t--;
}
}
printf("%lld
",ans);
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
a=read(),b=read(),c=read(),lx=read(),rx=read(),ly=read(),ry=read();
slove();
}
return 0;
}