SGU - 106 The equation（擴歐+細節處理）

傳送門

題目大意

給出 a x + b y + c = 0 ax+by+c=0 ax+by+c=0這一二元一次不定方程，求滿足 { ( x , y ) ∣ x ∈ [ l x , r x ] , y ∈ [ l y , r y ] } \{(x,y) | x \in [lx,rx],y\in [ly,ry]\} {(x,y)∣x∈[lx,rx],y∈[ly,ry]}解的個數，

解題思路

自以為寫了不少擴歐的題目，已經了如指掌，可是這道題又再次打臉， w a wa wa到懷疑人生…

首先不難想到如果 c c c挪到等式右邊仍然是負數那么應該將 c c c變號，與此同時 a , b a,b a,b也應該變號，但是此時 a , b a,b a,b的符號可能是負的，一開始我的想法是將符號提到自變數 x , y x,y x,y處，即 ∣ a ∣ ( ? x ) + ∣ b ∣ ( ? y ) = c |a|(-x)+|b|(-y)=c ∣a∣(?x)+∣b∣(?y)=c，然后求出特解后直接取負，這樣的做法不可以嗎？可以，但是在本題是不行的，原因如下：

因為我們要求的是在給定解空間下的解的個數，假設不考慮 a , b a,b a,b的符號那么上述方程化為 x = c ? b y a x = \frac{c-by}{a} x=ac?by?，當 a a a的符號改變后直接影響了最后的通解的形式發生改變，因此如果我們想對 a a a取負，正確的做法是對給出的解空間取反，也就是變成了 [ ? r x , ? l x ] [-rx,-lx] [?rx,?lx]，對于 y y y同理，

然后就是當我們解出通解后，需要得到解的個數，因為 x , y x,y x,y的變換是相反的，看起來似乎很難下手，但是實際上我們只需要根據通解的這個不等式 l x ≤ x 0 + k 1 b g c d ( a , b ) ≤ r x lx \leq x_0+k_1\frac{b}{gcd(a,b)} \leq rx lx≤x0?+k1?gcd(a,b)b?≤rx求出 x x x在解空間下 k 1 k_1 k1?的取值范圍，然后和 y y y的 k 2 k_2 k2?的取值范圍，二者取一個交集即可，此時需要再次注意，左邊應該向上取整，右邊向下取整，畫個圖就明白了，

還有就是需要特判 a = 0 , b = 0 a=0,b=0 a=0,b=0的三種情況

//
// Created by Happig on 2020/10/30
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "\n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 2e5 + 10;

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

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

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll a, b, c, lx, rx, ly, ry;
    cin >> a >> b >> c >> lx >> rx >> ly >> ry;
    c = -c;
    if (c < 0) c = -c, a = -a, b = -b;
    if (a < 0) a = -a, swap(lx, rx), lx = -lx, rx = -rx;
    if (b < 0) b = -b, swap(ly, ry), ly = -ly, ry = -ry;
    if (a == 0 && b == 0) {
        if (c == 0) cout << (rx - lx + 1) * (ry - ly + 1) << endl;
        else cout << 0 << endl;
        return 0;
    } else if (a == 0) {
        if (c % b == 0 && ly <= c / b && c / b <= ry) cout << rx - lx + 1 << endl;
        else cout << 0 << endl;
        return 0;
    } else if (b == 0) {
        if (c % a == 0 && lx <= c / a && c / a <= rx) cout << ry - ly + 1 << endl;
        else cout << 0 << endl;
        return 0;
    }
    ll d = gcd(a, b);
    if (c % d) {
        cout << "0" << endl;
    } else {
        ll x, y;
        exgcd(a, b, x, y);
        x = x * c / d, y = y * c / d;
        //cout << x << " " << y << endl;
        a /= d, b /= d;
        int l = max(ceil(1.0 * (lx - x) / b), ceil(1.0 * (y - ry) / a)), r = min(floor(1.0 * (rx - x) / b),
                                                                                 floor(1.0 * (y - ly) / a));
        if (r >= l) cout << r - l + 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}