[BalticOI 2024] Portal 题解

Ecrade_ · 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;
}