题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=106

题目大意

有一个方程ax + by + c = 0。 给定a,b,c,x1,x2,y1,y2,你需要得出,有多少整根满足以下条件: x1 <= x <= x2,y1 <= y <= y2。整根指一个整数对(x,y)。

题解

线性不定方程+不等式求解,特殊情况考虑 1.a=0 b=0; 2.a=0 b<>0; 3.a<>0 b=0.

题目看起来不难,做起来难,这题写了蛮久才过。从网上搜了很多题解,于是从头到尾也就看到三份不一样的代码,抄来抄去也不加点注释,或者解释一下关键语句的意思。

我主要卡在没有将a,b,c全部转化为正数,导致后面计算时出错,转换代码如下:

        c = -c;
        if (c < 0) {
            a = -a;
            b = -b;
            c = -c;
        }
        if (a < 0) {
            a = -a;
            long long t = x1;
            x1 = -x2;
            x2 = -t;
        }
        if (b < 0) {
            b = -b;
            long long t = y1;
            y1 = -y2;
            y2 = -t;
        }

知识点

拓展欧几里得算法解二元一次不定方程:a*x+b*y=c;

因为:gcd(a,b) | a , gcd(a,b) | b ; 

所以:gcd(a,b) | a*x,gcd(a,b) | b*y => gcd(a,b) | (a*x + b*y) => gcd(a,b) | c;

所以要求a*x+b*y=c,可以先求a*x+b*y=gcd(a,b),对于:a*x+b*y=gcd(a,b)

1.当b==0时,gcd(a,b)=a,此时x=1,y=0;

2.先求出 a*x+b*y=gcd(a,b) 的一组解。

因为 a*x1+b*y1=gcd(a,b) b*x2+a%by2=gcd(b,a%b) 且 gcd(a,b)=gcd(b,a%b); 

所以 a*x1+b*y1=b*x2+(a-(a/b)*b)*y2 从而得x1=y2,y1=x2-(a/b)*y2

如此递归得出一组解x0,y0; 

此时的解并非是原不定方程a*x+b*y=c的解并且gcd(a,b) | c

所以原不定方程的一组解 x1=x0*(c/gcd(a,b)),y1=y0*(c/gcd(a,b)); 

原不定方程有无数组解,并且又有a*(x+(b/gcd(a,b)))+b*(y-(a/gcd(a,b)))=gcd(a,b)

得到原不定方程的所有解为

x=x1+b/gcd(a,b)*t;

y=y2-a/gcd(a,b)*t;

(t=0,1,2,3,4,5...)

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

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

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 g = exgcd(b, a % b, x, y), t = x;
    x = y;
    y = t - a/b*y;
    return g;
}

int main() {
    long long a, b, c, x1, x2, y1, y2;
    scanf("%lld%lld%lld%lld%lld%lld%lld", &a, &b, &c, &x1, &x2, &y1, &y2);
    if (a == 0 && b == 0) {
        if (c == 0) printf("%lld\n", (x2 - x1 + 1)*(y2 - y1 + 1));
        else printf("0\n");
    } else if (a == 0) {
        if (c % b == 0 && c/b >= y1 && c/b <= y2) printf("%lld\n", x2 - x1 + 1);
        else printf("0\n");
    } else if (b == 0) {
        if (c % a == 0 && c/a >= x1 && c/a <= x2) printf("%lld\n", y2 - y1 + 1);
        else printf("0\n");
    } else {
        c = -c;
        if (c < 0) {
            a = -a;
            b = -b;
            c = -c;
        }
        if (a < 0) {
            a = -a;
            long long t = x1;
            x1 = -x2;
            x2 = -t;
        }
        if (b < 0) {
            b = -b;
            long long t = y1;
            y1 = -y2;
            y2 = -t;
        }
        long long x0, y0;
        long long g = exgcd(a, b, x0, y0);
        if (c % g) printf("0\n");
        else {
            a /= g;
            b /= g;
            c /= g;
            x0 *= c;
            y0 *= c;
            int xk1 = ceil((double)(x1 - x0)/b);
            int xk2 = floor((double)(x2 - x0)/b);
            int yk1 = ceil((double)(y0 - y2)/a);
            int yk2 = floor((double)(y0 - y1)/a);
            long long tk1 = max(xk1, yk1), tk2 = min(xk2, yk2);
            if (tk1 > tk2) printf("0\n");
            else printf("%lld\n", tk2 - tk1 + 1);
        }
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/6440 - 海胖博客