题目描述 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=1;y=0; 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>=0) return (int)x; return (int)(x-0.999999); } int Up(double x){ if(x>=0) 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 ");return; } if(a==0&&b==0){ if(c!=0)printf("0 "); else{ long long ans,li,ri; li=(long long)(q-p+1);ri=(long long)(s-r+1); ans=li*ri; cout<<ans<<endl; } return; } if(a==0){ if((int)(-c)%b==0&&(-c/(double)b)>=r&&(-c/(double)b)<=s)printf("1 "); else printf("0 "); return; } if(b==0){ if((int)(-c)%a==0&&(-c/(double)a)>=p&&(-c/(double)a)<=q)printf("1 "); else printf("0 "); return; } double x,y;int vgcd=exgcd(a,b,x,y); if((int)(-c)%vgcd!=0){ printf("0 ");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)+1>0)printf("%d ",min(x2,y2)-max(x1,y1)+1); else printf("0 "); } int main(){ int T;scanf("%d",&T); while(T--)work(); return 0; }