扩展欧几里得
通解:x+B/GCD*k,y+A/GCD*k
先缩小x1,x2范围，，再缩y
#include<bits/stdc++.h>using namespace std;void extgcd(long long a,long long b,long long &d,long long &x,long long &y)//return d=gcd(a,b)(==a*x+b*y){if(!b)d=a,x=1,y=0;else{extgcd(b,a%b,d,y,x);y-=x*(a/b);}}int main(void){//freopen("in","r",stdin);int t,Case=0;long long A,B,C,x1,x2,y1,y2;long long GCD,x,y;scanf("%d",&t);while(t–){scanf("%lld%lld%lld%lld%lld%lld%lld",&A,&B,&C,&x1,&x2,&y1,&y2);printf("Case %d: ",++Case);if(A==0&&B==0){if(C==0)printf("%lld\n",(x2-x1+1)*(y2-y1+1));elseprintf("0\n");continue;}if(A==0){if(C%B!=0){printf("0\n");continue;}y=-C/B;if(y1<=y&&y<=y2)printf("%lld\n",x2-x1+1);elseprintf("0\n");continue;}if(B==0){if(C%A!=0){printf("0\n");continue;}x=-C/A;if(x1<=x&&x<=x2)printf("%lld\n",y2-y1+1);elseprintf("0\n");continue;}extgcd(A,B,GCD,x,y);x*=-C/GCD;y*=-C/GCD;if(C%GCD!=0){printf("0\n");continue;}long long base1=B/GCD;long long base2=A/GCD;long long l,r;x1=((x-x1)%base1+abs(base1))%abs(base1)+x1;x2=((x-x2)%base1-abs(base1))%abs(base1)+x2;if(x1>x2){printf("0\n");continue;}l=(-base2)*((x1-x)/base1)+y;r=(-base2)*((x2-x)/base1)+y;if(l>r)swap(l,r);y1=max(y1,l);y2=min(y2,r);y1=((y-y1)%base2+abs(base2))%abs(base2)+y1;y2=((y-y2)%base2-abs(base2))%abs(base2)+y2;if(y1>y2)printf("0\n");elseprintf("%lld\n",(y2-y1)/abs(base2)+1);}return 0;}
游手好闲会使人心智生锈
