Gym102769I Interstellar Hunter 题解
题意：初始位置在 ((0,0)) 点，现在有两种操作：
- 操作 (1) ：你获得一种能力向量 ((x,y)) ，你可以从当前位置 ((a,b)) 出发，沿着这个能力向量方向移动任意整数个单位，即可以从 ((a,b)) 移动至 ((a+dx,b+dy)) ；
- 操作 (2) ：在二维平面上的某一点 ((x,y)) 上出现了一个价值为 (w) 的物品，如果你可以通过你当前拥有的能力向量移动至 ((x,y)) 就可以获得该物品。
问最终你可以获得的最大价值是多少？
题解：本题的核心思想是对于一系列的能力向量 ((x_0,y_0),(x_1,y_1),(x_2,y_2),cdots) 的线性组合，我们都可以通过两个基向量 ((bx,by)) 和 ((dx,0)) 的线性组合来得到，比较详细的证明请参考出题人在这个问题下的回答：
https://www.zhihu.com/question/426081900/answer/1535613903
因此我们需要维护这组基向量，使它能够表示所有能力向量的线性组合。
假设某一时刻，我们的基向量是 ((bx,by)) 和 ((dx,0)) ，现在加入了一个新的能力向量 ((x,y)) ，我们需要求解出新的基向量 ((bx',by')) 和 ((dx',0)) 。首先容易求得 (by'=gcd(by,y)) ，然后考虑 (dx') ，利用 ((bx,by)) 和 ((x,y)) 线性组合得到它们在 (x) 轴上的基向量：
[egin{aligned}
frac{y}{g}(bx,by)-frac{by}{g}(x,y)=(frac{1}{g}(ycdot bx-bycdot x),0)
end{aligned}
]
再和原先的基向量 ((dx,0)) 组合就能得出 (dx'=gcd(dx,frac{|ycdot bx - bycdot x|}{g})) 。
最后，我们通过 (exgcd) 求出 (bx') ：由裴蜀定理可以得出，存在 (a,bin Z) 使得 (acdot y+bcdot by=gcd(y,by)) ，因此我们可以通过 (exgcd) 求解该方程的一组解 ((a,b)) 并得到：(bx'=(acdot x+bcdot bx)mod{dx'}) 。
于是，我们就得到了一组新的基向量 ((bx',by')) 和 ((dx',0)) ，最后注意一下向量某一维为零的特殊情况即可。
#include <bits/stdc++.h>
using namespace std;
template<typename T>
T exgcd(T x, T y, T& a, T& b) {
if (!y) {
a = 1, b = 0;
return x;
}
T d = exgcd(y, x % y, b, a);
b -= x / y * a;
return d;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t; cin >> t;
for (int kase = 1; kase <= t; kase++) {
int n; cin >> n;
long long ans = 0;
long long bx = 0, by = 0, dx = 0;
for (int i = 0; i < n; i++) {
int op; cin >> op;
long long x, y, w;
if (op == 1) {
long long a, b;
cin >> x >> y;
long long g = exgcd(y, by, a, b);
dx = __gcd(dx, abs(y * bx - x * by) / g);
by = g;
bx = a * x + b * bx;
if (dx) {
bx = (bx % dx + dx) % dx;
}
}
else {
cin >> x >> y >> w;
if (by && y % by == 0) {
long long r = x - y / by * bx;
if (dx && r % dx == 0 || dx == r) {
ans += w;
}
}
else if (by == 0) {
if (bx && x % bx == 0 || bx == x) {
ans += w;
}
}
}
}
cout << "Case #" << kase << ": " << ans << '
';
}
return 0;
}