bzoj 5027: 数学题

.

题意：给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解有多少对？
题解：exgcd
求出一组解，求出满足x∈[x1,x2],y∈[y1,y2]的x和y相对求出来的是第几组（大概理解一下就好。。。）。取交集就好。注意特判，具体看代码。
代码：

#include<bits/stdc++.h>
#define pa pair<long long,long long>
#define l first
#define r second
using namespace std;

long long a,b,c,X1,X2,Y1,Y2;

long long exgcd(long long a,long long b,long long&x,long long&y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    long long tx,ty,d=exgcd(b,a%b,tx,ty);
    x=ty;
    y=tx-(a/b)*ty;
    return d;
}
long long wk(double x,long long type)
{
    if(type)
    return int(ceil(x));
    else
    return int(floor(x));
}
pa get(long long l,long long r,long long x,long long d)
{
    pa ans;
    if(l>=x)
    {
        ans.l=wk(1.0*(l-x)/d,d>0);
        ans.r=(r-x)/d;
    }
    else if(r<=x)
    {
        ans.l=(l-x)/d;
        ans.r=wk(1.0*(r-x)/d,d<0);
    }
    else
    {
        ans.l=(l-x)/d;
        ans.r=(r-x)/d;
    }
    if(d<0)
    swap(ans.l,ans.r);
    return ans;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&X1,&X2,&Y1,&Y2);
    if(a==0&&b==0)
    {
        if(!c)
        printf("%lld",(abs(X1-X2)+1)*(abs(Y1-Y2)+1));
        else
        puts("0");
        return 0;
    }
    long long x,y,d=exgcd(a,b,x,y);
    if(c%d)
    {
        puts("0");
        return 0;
    }
    long long t=-c/d;
    x*=t;
    if(b)
    y=(-c-a*x)/b;
    long long dx=b/d,dy=-a/d;
    if(dx==0)
    {
        if(dy==0)
        {
            if(x>=X1&&x<=X2&&y>=Y1&&y<=Y2)
            {
                puts("1");
                return 0;
            }
        }
        if(x>=X1&&x<=X2)
        printf("%lld",Y2-Y1+1);
        else
        puts("0");
        return 0;
    }
    else if(dy==0)
    {
        if(y>=Y1&&y<=Y2)
        printf("%lld",X2-X1+1);
        else
        puts("0");
        return 0;
    }
    else if((dx>0)==(dy>0))
    {
        dx=abs(dx);
        dy=abs(dy);
    }
    else if(dx<0)
    {
        dx=-dx;
        dy=-dy;
    }
    pa xx=get(X1,X2,x,dx),yy=get(Y1,Y2,y,dy);
    printf("%lld",max(0LL,min(xx.r,yy.r)-max(xx.l,yy.l)+1));
}