题目链接

SGU106

题目大意

已知a,b,c,xl,xr，求方程ax+by+c=0,x\in[xl,xr],\ y\in[yl,yr]的整数解个数.所有数不大于 10^8

解题思路

将上式转化成 ax+by=-c。令 c=-c，即 ax+by=c。 将此时的a,b,c变成正数：
如果 c<0，则 a,b,c 全部翻转；如果 a<0，则将 a 反转后，还需将区间 [xl,xr] 翻转；b<0 同理。
再特判含0的情况：a,b 均为 0，如果 c=0 则 a,b 可任取，否则无解；a=0，则看 by=c 是否有整数解，b=0 同理。
由扩展欧几里得，如果 c 不是 gcd(a,b) 的整数倍，则无解。a,b,c均除以gcd(a,b)，将然后利用扩展欧几里得解出一组x_0,y_0。那么x_0+kb,y_0-ka也是一组解。然后分别求出 k 在 [lx,rx],[ly,ry] 中的上下界（上界下取整，下界上取整），对两个上界取min、下界取max，交叉部分即为解的个数。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;
ll lx, rx;
ll ly, ry;
ll _x, _y;

ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0) {x = 1; y = 0; return a;}
    ll gcd = exgcd(b, a%b, x, y);
    ll t = x; x = y;
    y = t - a / b * y;
    return gcd;
}

int init()
{
    c = -c;
    if (c < 0) {a = -a; b = -b; c = -c;}
    if (a < 0) {a = -a; lx = -lx; rx = -rx; swap(lx, rx);}
    if (b < 0) {b = -b; ly = -ly; ry = -ry; swap(ly, ry);}
    if (a == 0 && b == 0) {
        if(c == 0) {
            printf("%lld\n", (rx - lx + 1) * (ry - ly + 1));
        }
        else puts("0");
        return 0;
    }
    if(a == 0) {
        if (c % b == 0 && c / b >= ly && c / b <= ry) {
            printf("%lld\n", rx - lx + 1);
        }
        else puts("0");
        return 0;
    }
    if(b == 0) {
        if (c % a == 0 && c / a >= lx && c / a <= rx) {
            printf("%lld\n", ry - ly + 1);
        }
        else puts("0");
        return 0;
    }
    ll g = gcd(a, b);
    if(c % g) {puts("0"); return 0;}
    a /= g; b /= g; c /= g;
    exgcd(a, b, _x, _y);
    _x *= c; _y *= c;
    return 1;
}

int main()
{
    scanf("%lld%lld%lld", &a, &b, &c);
    scanf("%lld%lld", &lx, &rx);
    scanf("%lld%lld", &ly, &ry);
    if(!init()) return 0;

    ll tmp1 = floor((double)(rx - _x) / b), tmp2 = floor((double)(_y - ly) / a);
    ll r = min(tmp1, tmp2);
    ll tmp3 = ceil((double)(lx - _x) / b), tmp4 = ceil((double)(_y - ry) / a);
    ll l = max(tmp3, tmp4);
    if(r < l) puts("0");
    else printf("%lld\n", r - l + 1);
    return 0;
}