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