题解 P2833 【等式】

· · 题解

啊。。。本蒟蒻de了一下午的bug终于A了。。。

关于拓展欧几里得：

我们看到ax+by=c这种形式的表达式就会想起扩展欧几里得（如果你不会的话建议先A了P1082 同余方程这道题再来），这里介绍一种简单的写法

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

很短吧，也很好理解，因为交换a,b的同时我们交换了x,y，所以原来辗转的方程被我们用引用简单地化解了。

题目分析：

这道题让我们求ax+by=-c在x,y一定限制下的解的个数，利用exgcd我们求出了一个特解ax_{0}+by_{0}=\gcd(a,b)，既然原来方程右边是-c，那我们两边都乘上\frac{-c}{\gcd(a,b)}就行了，即x_{0}=x_{0}\times \frac{-c}{\gcd(a,b)},y_{0}=y_{0}\times \frac{-c}{\gcd(a,b)}，然后我们现在有：

ax_{0}+by_{0}=-c

我们怎么得到原方程的通解呢？

先考虑在a>0,b>0的情况下，x在增加，y必然会减小，要让x增加一个整数的时候，y刚好也需要减小一个整数，很明显，当x增加b时，y减小a,即：

a(x_{0}+kb)+b(y_{0}-ka)=-c

但这不是最小的我们可以增加的那对整数，明显\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}是那对最小的整数，而方程：

a(x_{0}+k\frac{b}{\gcd(a,b)})+b(y_{0}-k\frac{a}{\gcd(a,b)})=-c

显然成立。所以我们原方程的解即为：

\begin{cases}x=x_{0}+k\frac{b}{\gcd(a,b)}\\y=y_{0}-k\frac{a}{\gcd(a,b)}\end{cases}

现在我们来考虑a<0,b<0的情况，将方程两边取反即可。

然后就是a<0\text{ xor }b<0的情况，比如a<0，我们可以设x^\prime=-x，那值域也要相应地取反，即

\begin{cases}x1^\prime=-x2\\x2^\prime=-x1\end{cases}

然后a=-a，又转变成a>0,b>0的情况了，b<0时同理。

最后我们解出k的取值范围，每一个k\in Z都对应着一对可行解，输出可行k\in Z的个数即可。

最后是特殊情况的总结：

  1. x1>x2\text{或}y1>y2$ 时 $ans=0
  2. > - $c=0$ 答案为$x,y$所有的组合（乘法原理） > - $c\neq 0 \Rightarrow ans=0
  3. > - $y1 \leq y_{0} \leq y2 \Rightarrow ans=\text{x的所有可能}
    • 否则 ans=0
  5. c\bmod\gcd(a,b)\ne 0 \Rightarrow ans=0
  6. k$的解集为$\emptyset$ 时 $ans=0

代码实现(50ms)：

#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll a, b, c, _x1, _x2, _y1, _y2;

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

void ans(ll val) { printf("％lld", val); exit(1); }

int main() {
    scanf("％lld％lld％lld％lld％lld％lld％lld",
        &a, &b, &c, &_x1, &_x2, &_y1, &_y2);
    if(_x1 > _x2 || _y1 > _y2) ans(0);
    c = -c;//移项
    if(!a && !b) {
        if(c) ans(0);
        else ans((_x2 - _x1 + 1) * (_y2 - _y1 + 1));
    }
    if(a < 0 && b < 0) a = -a, b = -b, c = -c;
    else if(a < 0) swap(_x1, _x2), _x1 = -_x1, _x2 = -_x2, a = -a;
    else if(b < 0) swap(_y1, _y2), _y1 = -_y1, _y2 = -_y2, b = -b;
    ll x, y, gcd;
    exgcd(a, b, x, y, gcd);
    if(c % gcd) ans(0);
    c /= gcd; x *= c; y *= c;
    if(!a) (_y1 <= y && y <= _y2) ? ans(_x2 - _x1 + 1) : ans(0);
    if(!b) (_x1 <= x && x <= _x2) ? ans(_y2 - _y1 + 1) : ans(0);
    double l = double(gcd * (_x1 - x)) / b;//x范围定界
    double r = double(gcd * (_x2 - x)) / b;
    l = fmax(l, double(gcd * (y - _y2)) / a);//y范围定界
    r = fmin(r, double(gcd * (y - _y1)) / a);
    int ansl = ceil(l), ansr = floor(r);//注意边界取整
    ans(ansr >= ansl ? ansr - ansl + 1 : 0);
    return 0;
}

网上复制粘贴谁不会啊