Description

There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the following conditions : x1<=x<=x2,   y1<=y<=y2. Integer root of this equation is a pair of integer numbers (x,y).

Input

Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks. All numbers are not greater than 108 by absolute value。

Output

Write answer to the output.

Sample Input

1 1 -3
0 4
0 4

Sample Output

4
这题思路很明显，就是直接扩展欧几里得，想当时扩展欧几里得看了将近一天的书才看懂，毕竟智商压制啦；

当时我看到这题，用扩展欧几里得算出x0,y0之后不能用循环来求k；

只能用通项公式

x=x0+k*b;

y=y0-k*a;

我一般喜欢把a变成a/d，b也是；

求出k的取值范围，这地方要注意，因为是整数除法，所以要注意漏掉的情况；

然后这题比较蛋疼的就是要注意a，b，c为0的情况；

分为4种情况

1:a为0，b不为0；

2:a不为0，b为0

3:a，b为0，c不为0

4:a,b,c都为0；

贴下ac代码，讲道理，写了好久，又调试了很久

看着跑的数据从1，导2，再到8最后ac的时候特别爽；

#include<cstdio>
#include<iostream>
#include<cstring>
#define debug(x) cout<<#x<<"="<<x<<endl;
using namespace std;
__int64 exgcd(__int64 a,__int64 b,__int64& x,__int64& y)
{
    if(!b) {
        x=1;y=0;return a;
    }
    __int64 d=exgcd(b,a%b,x,y);
    __int64 t=x;
    x=y;
    y=t-a/b*y;
    return d;
}
int main()
{
    __int64 a,b,c;
    __int64 x1,x2,y1,y2;
    __int64 x0,y0;
    double k1,k2;
    __int64 maxx,maxy,minx,miny;
    //freopen("input.txt","r",stdin);
    while(~scanf("%I64d%I64d%I64d %I64d%I64d %I64d%I64d",&a,&b,&c,&x1,&x2,&y1,&y2))
    {
        __int64 d=exgcd(a,b,x0,y0);
        if(!a&&b&&-c/b<=y2&&-c/b>=y1)
        {
            if(c%b) printf("0\n");
            else printf("%I64d\n",y2-y1+1);
            continue;
        }
        if(!b&&a&&-c/a<=x2&&-c/a>=x1)
        {
            if(c%a) printf("0\n");
            else printf("%I64d\n",x2-x1+1);
            continue;
        }
        if(!b&&!a&&!c)
        {
            __int64 x=x2-x1+1;
            __int64 y=y2-y1+1;
            printf("%I64d\n",x*y);
            continue;
        }
        if(!b&&!a&&c)
        {
            printf("0\n");
            continue;
        }
        if(c%d){
            printf("0\n");
            continue;
        }
        x0*=-c/d;y0*=-c/d;
        a=a/d;b=b/d;
        k1=(x1-x0)*1.0/b;
        k2=(x2-x0)*1.0/b;
        maxx=k1>k2?k1:k2;
        minx=k1>k2?k2:k1;
        if(minx<k1&&minx<k2)
            minx++;
        if(maxx>k1&&maxx>k2)
            maxx--;
        k1=(y0-y1)*1.0/a;
        k2=(y0-y2)*1.0/a;
        maxy=k1>k2?k1:k2;
        miny=k1>k2?k2:k1;
        if(miny<k1&&miny<k2)
            miny++;
        if(maxy>k1&&maxy>k2)
            maxy--;
            minx=max(minx,miny);
            maxx=min(maxx,maxy);
            if(maxx-minx<0)
                printf("0\n");
            else printf("%I64d\n",maxx-minx+1);
    }
    return 0;
}

女神收尾