题目描述 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
/*
扩展欧几里得
再复习一遍有关公式:
推导过程： a*x1+b*y1=gcd(a,b)
b*x2+(a%b)*y2=gcd(a,b) => b*x2+(a-b*(a/b))*y2=gcd(a,b) => a*y2+b*(x2-(a/b)*y2)=gcd(a,b)
可得：x1=y2,y1=x2-(a/b)*y2
转变成需要的x和y：x=x*c/gcd(a,b),y=y*c/gcd(a,b)
（注意：当 c%gcd(a,b)!=0 时，无解）
转变成一般的x和y：x=x+t*(b/gcd),y=y+t*(a/gcd) 快WA成SB了
要特判的情况太多了 （a=0&&b=0,a=0,b=0)
*/
#include<cstdio>
#include<iostream>
using namespace std;
int exgcd(int a,int b,double &x,double &y){
if(!b){
x=;y=;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*y;
return r;
}
int Down(double x){
if(x>=) return (int)x;
return (int)(x-0.999999);
}
int Up(double x){
if(x>=) return (int)(x+0.999999);
return (int)x;
}
void work(){
int a,b;double c,p,q,r,s;
scanf("%d%d%lf%lf%lf%lf%lf",&a,&b,&c,&p,&q,&r,&s);
if(p>q||r>s){
printf("0\n");return;
}
if(a==&&b==){
if(c!=)printf("0\n");
else{
long long ans,li,ri;
li=(long long)(q-p+);ri=(long long)(s-r+);
ans=li*ri;
cout<<ans<<endl;
}
return;
}
if(a==){
if((int)(-c)%b==&&(-c/(double)b)>=r&&(-c/(double)b)<=s)printf("1\n");
else printf("0\n");
return;
}
if(b==){
if((int)(-c)%a==&&(-c/(double)a)>=p&&(-c/(double)a)<=q)printf("1\n");
else printf("0\n");
return;
}
double x,y;int vgcd=exgcd(a,b,x,y);
if((int)(-c)%vgcd!=){
printf("0\n");return;
}
x=x*(-c)/(double)vgcd;y=y*(-c)/(double)vgcd;
double tx1=(p-x)*(double)vgcd/b,tx2=(q-x)*(double)vgcd/b;
double ty1=(y-s)*(double)vgcd/a,ty2=(y-r)*(double)vgcd/a;
if(tx1>tx2)swap(tx1,tx2);if(ty1>ty2)swap(ty1,ty2);
int x1=Up(tx1),x2=Down(tx2),y1=Up(ty1),y2=Down(ty2);
if(min(x2,y2)-max(x1,y1)+>)printf("%d\n",min(x2,y2)-max(x1,y1)+);
else printf("0\n");
}
int main(){
int T;scanf("%d",&T);
while(T--)work();
return ;
}