H - The equation——(SGU 106)

  1. 云栖社区>
  2. 博客>
  3. 正文

H - The equation——(SGU 106)

angel_imp 2016-03-19 19:20:00 浏览805
展开阅读全文

传送门
Password:nefu


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

题目大意:
给出a,b,c,x1,x2,y1,y2,求满足ax+by+c=0,且x∈[x1,x2],y∈[y1,y2]的整数解个数。

解题思路:
首先想到这是一个扩展欧几里得的题,扩展欧几里得有模板,扩展欧几里得求解的是ax+by=c,而本题是ax+by+c=0,需将c移项,然后我们需要注意的就是特判一些数据,比如说 0 的情况分别当 a,b,c==0的时候判断一下子,然后剩下的就是一些细节问题啦,当c 不能整除 GCD(a,b)的时候就是0,还有考虑a和b的正负问题,等等,具体的细节都在代码里

上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;

#define MM(a) memset(a,0,sizeof(a))

typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 1e7+5;
const int mod = 1000000007;
const double eps = 1e-7;

void Ex_gcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b)*y1;
}
LL GCD(LL a, LL b)
{
    if(b == 0)
        return a;
    return GCD(b, a%b);
}
int main()
{
    LL a, b, c, x, y, x1, x2, y1, y2, lx, ly, rx, ry, dx, dy, p;
    while(cin>>a>>b>>c)
    {
        cin>>x1>>y1>>x2>>y2;
        c = -c;
        if(x1>y1 ||x2>y2)
            puts("0");
        else if(a==0 && b==0 && c==0)
            cout<<(y1-x1+1)*(y2-x2+1)<<endl;
        else if(a==0 && b==0)
            puts("0");
        else if(a == 0)
        {
            if(c%b || c/b>y2 || c/b<y1)
                puts("0");
            else
                printf("%lld\n",y1-x1+1);
        }
        else if(b == 0)
        {
            if(c%a || c/a>x2 || c/a<x1)
                puts("0");
            else
                printf("%lld\n",y2-x2+1);
        }
        else
        {
            LL d = GCD(abs(a), abs(b));
            if(c % d)
                puts("0");
            else
            {
                a /= d;
                b /= d;
                c /= d;
                Ex_gcd(abs(a), abs(b), x, y);
                x *= c, y *= c;
                ///cout<<x<<" "<<y<<" "<<endl;
                if(a < 0)
                    x = -x;
                if(b < 0)
                    y = -y;
                dx = abs(b), dy = abs(a);
                p = (x%dx-x1%dx+2*dx) % dx;
                lx = x1 + p;
                ///cout<<lx<<endl;0
                p = (x%dx-y1%dx+2*dx) % dx;
                rx = y1 + p - (p == 0 ? 0 : dx);
                ///cout<<rx<<endl;
                if(lx > rx)
                    puts("0");
                else
                {
                    ly = (c-a*lx) / b, ry = (c-a*rx) / b;
                    if(ly > ry)
                        swap(ly, ry);
                    if(ly > y2 || ry < x2)
                        puts("0");
                    else
                    {
                        if(ly < x2)
                        {
                            p = (y%dy-x2%dy+2*dy) % dy;
                            ly = x2 + p;
                        }
                        if(ry > y2)
                        {
                            p = (y%dy-y2%dy+2*dy) % dy;
                            ry = y2 + p - (p == 0 ? 0 : dy);
                        }
                        printf("%lld\n", (ry - ly) / dy + 1);
                    }
                }
            }
        }
    }
    return 0;
}

网友评论

登录后评论
0/500
评论
angel_imp
+ 关注