2020CCPC秦皇岛 I. Interstellar Hunter

给出一系列二维向量(x_i,y_i)~(0 \leq x_i,y_i \leq 10^6)，问一个给定向量(x,y)是否可以被这些向量的整数组合表示。

首先显然向量组\{\boldsymbol{a}, \boldsymbol{b}\}与向量组\{\boldsymbol{a} \pm \boldsymbol{b}, \boldsymbol{b}\} 以及向量组 \{\boldsymbol{a}, \boldsymbol{b} \pm \boldsymbol{a}\}所能生成的点集等价。

于是若已知向量组\{\boldsymbol{a}=(x_1,y_1), \boldsymbol{b}=(x_2,y_2)\}，设g = (y_1, y_2)，那么我们可以通过类似辗转相除的方法将向量组变成\{(tx_1, 0), (tx_2, g) \}。其中

\displaystyle tx_1 = \frac{y_2}{g}x_1 - \frac{y_1}{g}x_2, tx_2 = ax_1 + bx_2, ay_1 + by_2 = g

再加入一个新向量(x_3,y_3)时，可以继续把该向量与向量(tx_2,g)变换成(x,0)和(tx_3,(g,y_3))，其中向量(x,0)可以和之前的向量(tx_1,0)通过gcd合并。

于是我们可以维护一个大小为2的与输入向量等价的向量基来进行判断。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1; y = 0; return a;
    }
    ll ret = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
int main(){
    int t, cas = 0;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        ll x = 0, y = 0, d = 0, ans = 0;
        while(n--){
            ll opt, tx, ty, w;
            scanf("%lld%lld%lld", &opt, &tx, &ty);
            if(opt == 1){
                if(ty == 0){
                    d = __gcd(d, abs(tx));
                    continue;
                }
                if(ty < 0) ty *= -1, tx *= -1;
                ll g, a, b;
                g = exgcd(y, ty, a, b);
                d = __gcd(abs(x * ty / g - tx * y / g), d);
                y = g;
                x = a * x + b * tx;
                if(d) x = (x % d + d) % d;
            }
            else{
                scanf("%lld", &w);
                if(y == 0){
                    if(d == 0){
                        if(tx == 0 && ty == 0)
                            ans += w;
                    }
                    else if(tx % d == 0 && ty == 0)
                        ans += w;
                }
                else if(ty % y == 0){
                    if(d && (tx - ty / y * x) % d == 0)
                        ans += w;
                    else if(!d && !(tx - ty / y * x))
                        ans += w;
                }
            }
        }
        cout << "Case #" << ++cas << ": " << ans << endl;
    }
    return 0;
}