给出一系列二维向量(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;
}