自动搬运

查看原文

来自洛谷，原作者为

	saxiy How can we rewrite the stars?

搬运于2025-08-24 21:42:05，当前版本为作者最后更新于2019-08-29 19:53:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

啊。。。本蒟蒻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. $a=0 \text{且} b=0$ 时：

• $c=0$ 答案为$x,y$所有的组合（乘法原理）
• $c\neq 0 \Rightarrow ans=0$

3. $a=0$ 时：

• $y1 \leq y_{0} \leq y2 \Rightarrow ans=\text{x的所有可能}$
• 否则 $ans=0$

4. $b=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;
}

网上复制粘贴谁不会啊