本文共 2126 字，大约阅读时间需要 7 分钟。

题意

给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解有多少对？

题解

就一个裸的扩展欧几里得。。。
但是要特判的情况有点多。。
为了方便，我固定了一开始的x是刚刚好小于x1的
这样的话情况会少一点

CODE:

#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>using namespace std;typedef long long LL;LL exgcd (LL a,LL b,LL &x,LL &y){    if (a==0)   {  y=1;x=0;return b;}    LL tx,ty;    LL d=exgcd(b%a,a,tx,ty);    x=ty-(b/a)*tx;y=tx;    return d;}int main(){    LL a,b,c,x1,x2,y1,y2;    scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x1,&x2,&y1,&y2);    if (x1>x2||y1>y2)    {        printf("0");        return 0;    }    c=-c;    if (a==0&&b==0)    {        if (c!=0)  printf("0\n");        else printf("%lld\n",max(0LL,(x2-x1+1)*(y2-y1+1)));        return 0;    }    if (a==0)    {        LL g=c/b;        if (g*b==c&&g>=y1&&g<=y2) printf("%lld\n",max(0LL,x2-x1+1));        else printf("0");        return 0;    }    if (b==0)    {        LL g=c/a;        if (g*a==c&&g>=x1&&g<=x2) printf("%lld\n",max(0LL,y2-y1+1));        else printf("0");        return 0;    }    //ax+by=-c;    LL x,y;    LL d=exgcd(a,b,x,y);    if (c%d!=0) {  printf("0\n");return 0;}    x=(x*(c/d)%(b/d)+(b/d))%(b/d);      LL xx=b/d,yy=-a/d;//两个东西    if (xx<0) {xx=-xx;yy=-yy;}    //每一次可以变多少     if (x>=x1)    {        LL t=(x-x1)/xx;//先变下来        x=x-t*xx;if (x>=x1) x-=xx;    }    else    {        LL t=(x1-x-1)/xx;        x=x+t*xx;    //  printf("OZY:%d\n",x);        if (x+xx<x1) x+=xx;    }    y=(c-a*x)/b;//先解出两个解//  printf("YES:%lld %lld %lld %lld\n",x,y,xx,yy);    LL ans=(x2-x)/xx;//x范围可以变大多少    if (y>y2)//要缩小     {        if (yy>0) ans=0;        else        {        //  printf("YES\n");            LL lalal=(y1-y)/yy;            ans=min(ans,lalal);            ans=ans-(y2-y+1)/yy;        }    }    else if(y<y1)//要变大    {        if (yy<0) ans=0;        else        {        //  printf("YES\n");            LL lalal=(y2-y)/yy;            ans=min(ans,lalal);            ans=ans-(y1-y-1)/yy;        }    }    else//随便变？     {    //  printf("YES\n");        if (yy>0) ans=min(ans,(y2-y)/yy);        else ans=min(ans,(y1-y)/yy);    }    ans=max(ans,0LL);    printf("%lld\n",ans);    return 0;}