自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 23:00:57，当前版本为作者最后更新于2024-07-24 02:13:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

可将题意转化为：$\forall 1\le i,j\le n$，$\forall \Delta x,\Delta y\in \mathbb{Z}$ 都有 $c(x_i+\Delta x,y_i+\Delta y)=c(x_j+\Delta x,y_j+\Delta y)$，其中 $c(x,y)$ 表示 $(x,y)$ 位置格子的颜色。

注意到我们只关心传送门之间的相对位置，因此方便起见，不妨将某个传送门移动到原点，并移动其余传送门使各传送门之间的相对位置保持不变。将移动后的新坐标记为 $(x'_i,y'_i)$。

不难发现，$\forall 1\le i,j\le n,i\neq j$，$\forall k\in\mathbb{Z}$，将 $(x'_i,y'_i)$ 变为 $(x'_i+k\cdot x'_j,y'_i+k\cdot y'_j)$ 后，答案不变。因此，可以使用欧几里得算法将 $n-1$ 个传送门的 $y$ 坐标变为 $0$，此时这 $n-1$ 个传送门可以等价于一个新的传送门，$x$ 坐标为它们 $x$ 坐标绝对值的最大公约数，$y$ 坐标为 $0$。

这样，我们成功地将 $n$ 个传送门等价为了 $3$ 个形如 $(0,0),(a,0),(b,c)$ 的传送门，不难得出答案即为 $|ac|$。特别地，当 $|ac|=0$ 时，则说明可以使用无数种颜色，需输出 $-1$。

时间复杂度为 $O(n\log V)$，其中 $V$ 为值域。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll n,x,y,dx,dy,fx,tx,ty;
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
ll myabs(ll x){return x < 0 ? -x : x;}
void work(ll x,ll y){
	if (y < 0) x = -x,y = -y;
	while (ty){
		ll qwq = y / ty;
		x -= qwq * tx,y -= qwq * ty;
		swap(x,tx),swap(y,ty);
	}
	fx = __gcd(fx,myabs(tx)),tx = x,ty = y;
}
int main(){
	n = read();
	for (ll i = 1;i <= n;i += 1){
		if (i == 1){dx = read(),dy = read(); continue;}
		x = read(),y = read(),work(x - dx,y - dy);
	}
	if (!fx || !ty) puts("-1");
	else printf("%lld",(long long) (fx * myabs(ty)));
	return 0;
}