SGU 106 The equation

106. The equation

time limit per test: 0.25 sec.
memory limit per test: 4096 KB

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

传送门

http://codeforces.com/problemsets/acmsguru/problem/99999/106

题目大意

你有这么一个方程ax+by+c=0，现在给你a,b,c，再给定x1,x2,y1,y2，询问有几组整数解使得x1<=x<=x2,y1<=y<=y2。

思路

细节比较多的一题，调代码调到吐了。

这道题是在限制条件下求解可行解，先把较为简单情况求出来。

当$c \% gcd(a,b)!=0$，不存在解。
当$a=0,b=0$时，若$c!=0$，无解，若$c=0$，输出$(r_1-l_1+1)*(r_2-l_2+1)$。
当$a=0,b!=0$时，即解方程$by+c=0$，若解出的$y$符合条件，则输出$r_2-l_2+1$，否则输出0。
当$a!=0,b=0$时，同第三种情况。

最后只剩下一种情况了$ax+by=c,(c已经取过负号)$有解，为了方便处理这种情况，我们把系数的符号统一为正。

若$c<0$，把方程两边同时乘上-1.
若$a<0$，把$a$转化为正数，其时相当于把$a$的负号给$x$，此时为$a*(-x)$，即$l_1leq -xleq r_1$，所以此时$x$的范围也要变号。
同第二种情况。
通过求解$ax+by=c$，得到一组解$x_0,y_0$。
求解 $ l_1leq x_0+k*frac{b}{d}leq r_1$和$ l_2leq y_0-k*frac{a}{d}leq r_2$。所求得的左区间要向上取整，右区间要向下取整。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;



ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll z = x;
    x = y;
    y = z - (a / b) * y;
    return d;

}

ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()

{
    ll a, b, c, l1, r1, l2, r2;
    cin >> a >> b >> c >> l1 >> r1 >> l2 >> r2;

    if(a == 0 && b == 0)
    {
        if(c == 0)
        {
            printf("%lld
", (r1 - l1 + 1) * (r2 - l2 + 1) );
        }
        else
        {
            printf("0
");
        }
    }
    else if(a == 0 && b)
    {
        c = -c;
        if((c / b) >= l2 && (c / b) <= r2 )
        {
            printf("%lld
", r1 - l1 + 1 );
        }
        else
        {
            printf("0
");
        }
    }
    else if(a && b == 0)
    {
        c = -c;

        if((c / a) <= r1 && (c / a) >= l1)
        {
            printf("%lld
", r2 - l2 + 1 );
        }
        else
        {
            printf("0
");
        }
    }
    else
    {
        if(c % gcd(a, b))
        {
            printf("0
");
        }
        else
        {
            c = -c;

            if(c < 0)
            {
                c = -c;
                a = -a;
                b = -b;
            }
            if(a < 0)
            {
                a = -a;
                swap(l1, r1);
                l1 = -l1;
                r1 = -r1;
            }

            if(b < 0)
            {
                b = -b;
                swap(l2, r2);
                l2 = -l2;
                r2 = -r2;
            }


            ll x, y;

            ll d = exgcd(a, b, x, y);
            x = x * c / d;
            y = y * c / d;

            //    l1=<x+k*b/d<=r1
            //    l2=<y-k*a/d<=r2


            double tx = x, ty = y;
            double tl1 = l1, tl2 = l2;
            double tr1 = r1, tr2 = r2;

            double ta = a / d;
            double tb = b / d;


            ll kr = min(floor(((tr1 - tx) / tb)), floor(((ty - tl2) / ta)));

            ll kl = max(ceil(((tl1 - tx) / tb)), ceil(((ty - tr2) / ta)));

            if (kr < kl)
                printf("0
");
            else
                printf("%lld", kr - kl + 1);


        }
    }
}