2020秦皇岛CCPC 7-9 Interstellar Hunter（扩展欧几里得，向量）

题意： 起始位置(0,0)，给你一些(a,b)，代表你可以移动(a,b)或者(-a,-b)，可以无限操作。 每次再询问能否到达某个点(x,y)。

思路： 将点看作向量，假设初始只有一个向量$A$，则当前询问能否到达$X$向量，要满足$X=k\ast A,(k\in Z)$，此时是否存在解是确定的。

如果初始两个向量$B$，则询问$X$向量，有$X=k1\ast A+k2\ast B,(k1,k2\in Z)$ 此时对等式右边进行辗转相除（欧几里得）变换得到$X=k1\ast A^{{}^{\prime }}+k2\ast B^{{}^{\prime }},(k1,k2\in Z)$，使得此时$A.x=0$。因为只可能有$B$向量的$x$坐标值，所以$k2$的值是确定的，此时就能通过看能否找到$k1$，判断是否有解。

如果再加入一个向量$C$，则询问$X$向量，变成了$X=k1\ast A^{{}^{\prime }}+k2\ast B^{{}^{\prime }}+k3\ast C,(k1,k2,k3\in Z)$。同理我们想使得只有一个向量只有$x$轴坐标，因为这样才能确定答案。所以我们将$B^{{}^{\prime }}$和$C$进行辗转相除，使得$B^{{}^{\prime }}.x=0$。

最后得到$X=k1\ast A^{{}^{\prime }}+k2\ast B^{{}^{\prime \prime }}+k3\ast C^{{}^{\prime }},(k1,k2,k3\in Z)$，此时$k2$的值是确定的，我们要找对应的$k1,k3$。 因为$A^{{}^{\prime }}$和$C^{{}^{\prime }}$向量都只有y轴坐标值，所以可以化为$X.y=k1\ast A{}^{\prime }.y+k3\ast C{}^{\prime }.y$，这就是扩展欧几里得求解多元等式。解存在的条件是$X.y|gcd(A{}^{\prime }.y,C{}^{\prime }.y)$。所以可以将$A{}^{\prime }$向量和$C{}^{\prime }$向量合成一个东西$A{}^{\prime \prime }$，满足$A{}^{\prime \prime }.x=0，A{}^{\prime \prime }.y=gcd(A{}^{\prime }.y,C{}^{\prime }.y)$。

最后等式合并成$X=k1\ast A{}^{\prime \prime }+k2\ast B{}^{\prime \prime }，(k1,k2\in Z）$。 此时和两个向量的情况是一样的，因为只有一个向量的x轴坐标有值，所以可以直接判断是否有解。更多向量的情况可以依次类推。

---

由这道题，我们甚至可以得到本题的多维向量的解法。我们只要将得到的向量进行辗转相除，使得只有一个向量第一维度有值，只有一个向量第二维度有值。。。就可以依次的确定每个向量的系数，并判断是否存在这样的系数。

以3维向量举例

1个向量：$A(x,y,z)$ 2个向量：$A(0,y,z),B(x,y,z)$，A,B辗转相除 3个向量：$A(0,0,z),B(0,y,z),C(x,y,z)$，C,B辗转相除，然后A,B辗转相除 4个向量：$A(0,0,z),B(0,0,z),C(0,y,z),D(x,y,z)$, =》$A(0,0,gcd(A.z,B.z)),C(0,y,z),D(x,y,z)$ C,D辗转相除，B,C辗转相除，A,B取GCD。 …

#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; struct Node { ll x,y; Node(){ this -> x = 0; this -> y = 0; }; Node(ll x,ll y) { this -> x = x; this -> y = y; } Node operator * (const ll &t) const { return Node(x * t,y * t); } Node operator - (const Node &rhs) const { return Node(x - rhs.x,y - rhs.y); } }; void zhanzhuan(Node &a,Node &b) { while(a.x != 0) { ll t = b.x / a.x; b = b - a * t; swap(a,b); } } ll gcd(ll n,ll m) { return m == 0 ? n : gcd(m,n % m); } ll lcm(ll n,ll m) { return n / gcd(n,m) * m; } int main() { int T;scanf("%d",&T); int kase = 0; while(T--) { ll ans = 0; Node px,py; int op; Node now; int n;scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d%lld%lld",&op,&now.x,&now.y); if(op == 1) { zhanzhuan(now,px); if(now.y) py.y = gcd(py.y,now.y); if(py.y) { px.y %= py.y; } } else { int val;scanf("%d",&val); if(now.x) { if(px.x == 0 || now.x % px.x != 0) continue; ll t = now.x / px.x; now.y -= t * px.y; } if(now.y == 0) ans += val; else if(py.y && now.y % py.y == 0) ans += val; } } printf("Case #%d: %lld\n",++kase,ans); } return 0; }