本文共 2958 字，大约阅读时间需要 9 分钟。

题目大意

给出$ax+by+c=0$这一二元一次不定方程，求满足$\{$

解题思路

自以为写了不少扩欧的题目，已经了如指掌，可是这道题又再次打脸，$wa$到怀疑人生…

首先不难想到如果$c$挪到等式右边仍然是负数那么应该将$c$变号，与此同时$a,b$也应该变号，但是此时$a,b$的符号可能是负的。一开始我的想法是将符号提到自变量$x,y$处，即$|a|(-x)+|b|(-y)=c$，然后求出特解后直接取负。这样的做法不可以吗？可以，但是在本题是不行的，原因如下：

因为我们要求的是在给定解空间下的解的个数，假设不考虑$a,b$的符号那么上述方程化为$x=\frac{c-by}{a}$，当$a$的符号改变后直接影响了最后的通解的形式发生改变，因此如果我们想对$a$取负，正确的做法是对给出的解空间取反，也就是变成了$[-rx,-lx]$，对于$y$同理。

然后就是当我们解出通解后，需要得到解的个数，因为$x,y$的变换是相反的，看起来似乎很难下手，但是实际上我们只需要根据通解的这个不等式$lx\le x_0+k_1\frac{b}{gcd(a,b)}\le rx$求出$x$在解空间下$k_1$的取值范围，然后和$y$的$k_2$的取值范围，二者取一个交集即可。此时需要再次注意，左边应该向上取整，右边向下取整，画个图就明白了。

还有就是需要特判$a=0,b=0$的三种情况

//// Created by Happig on 2020/10/30//#include 
   
    #include 
    
     #include 
     
      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
      
        pii;typedef pair
       
         pll;typedef pair
        
          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;}