POI Knights

题目链接

题目大意

有$n(n\le 100)$个二元组描述了一个骑士的行进方式，遵从如下规则：

若二元组为$(a,b)$，则骑士从$(x,y)$出发可以到达$(x+a,y+b)$或$(x-a,y-b)$

两个二元组集合是等价的当且仅当有一个从$(0,0)$出发的骑士，经过任意次行进，通过这两组二元组所能到达的格子完全相同。
可以看出对于任何一个二元组集合，都有一个大小为2的集合与它等价，求这个大小为2的集合。

思路

首先可以证明这个集合肯定存在：

将这些行走方式看做一个个向量，则一定存在一组基底可以通过线性组合表示这些向量，因为是二维空间，故基底的个数为2

然后考虑如何求这一组基底。
找一组简单的数据画图可以发现，对于一个固定的横坐标，这一列上所有的点的纵坐标的间距是相等的，同时更换横坐标时这个间距不变。又可以看出，只有某些横坐标才会有点，并且这些横坐标的间距也是相等的。
先考虑求纵坐标上的间距，设间距为$y$有如下推导：
设两向量分别为$(a_1,b_1),(a_2,b_2)$，两向量系数分别为$t_1,t_2$。
先考虑最简单的情景，该点在$y$轴上，我们求$(0,0)$点正上方的那个点。则可以列出如下式子。

$$\begin{cases} t_1a_1+t_2a_2=0\\ \\ t_1b_1+t_2b_2=y \end{cases}$$
将第一个式子移项得
$$\frac{t_1a_1}{a_2}=-t_2$$
$t_2$显然是整数（骑士是不是肯定不能走半步），故
$$a_2\ \Big|\ t_1a_1$$
这个式子的形式并不能说明什么，我们两边同除 $\gcd(a_1,a_2)$，得
$$\frac{a_2}{\gcd(a_1,a_2)}\ \Big|\ \frac{t_1a_1}{\gcd(a_1,a_2)}$$
设 $a_1'=\frac{a_1}{\gcd(a_1,a_2)},a_2'=\frac{a_2}{\gcd(a_1,a_2)}$，可得 $\gcd(a_1',a_2')=1$，故
$$a_2'\ \Big|\ t_1$$
故 $t_1=k\frac{a_2}{\gcd(a_1,a_2)}$
同理 $t_2=k\frac{a_1}{\gcd(a_1,a_2)}$，此处 $t_1,t_2$异号。
带回原式得
$$k*\frac{a_1b_2-a_2b_1}{\gcd(a,b)}=y$$
正上方的点， $k=1$，所以有 $y=\frac{a_1b_2-a_2b_1}{\gcd(a_1,a_2)}$
求出了这个间距，不禁让我们有了一些想法。

能不能将任意的两个向量（非共线），找到另两个等价向量，满足其中一个与$y$轴平行？

答案是可以的。怎么做呢？
其中一个向量肯定是$(0,\frac{a_1b_2-a_2b_1}{\gcd(a_1,a_2)})$，另一个是用来控制横坐标改变和随之而来的纵坐标改变的。
这个向量是$(\gcd(a_1,a_2),y)$，现在我们来求这个$y$。
这个向量的横坐标可以看成是由最初的两个向量按比例缩放而成的，故纵坐标也应该是它按比例缩放的。
让我们想起了一个熟悉的式子。
$$a_1x+a_2y=\gcd(a_1,a_2)$$
熟悉不？其中$x,y$就是缩放的比例。扩展欧几里得即可求解。
则第二个坐标为$b_1x+b_2y$。

由此我们得到了一个算法：每次找到两个向量，把其中一个变成与$y$轴平行，另一个继续扔回向量堆中。继续重复算法，直到只剩一个不与$y$轴平行。此时有一大堆和$y$轴平行的向量，我们对其纵坐标取一个$\gcd$，即是最终的答案之一，另一个就是剩下的那个没有做此算法的向量。

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define pa pair
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_backusing namespace std;inline ll read()
{long long f=1,sum=0;char c=getchar();while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}return sum*f;
}
const int MAXN=110;
ll exgcd(ll a,ll b,ll &x,ll &y)
{if (!b){x=1,y=0;return a;}ll tmp,ret;ret=exgcd(b,a%b,x,y);tmp=x;x=y;y=tmp-a/b*y;return ret;
}
int _gcd(int a,int b)
{if (!b) return a;return _gcd(b,a%b);
}
int a[MAXN],b[MAXN];
int main()
{int n;scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);for (int i=2;i<=n;i++){ll x,y;ll gcd=exgcd(a[i-1],a[i],x,y);ll tmpa1=0,tmpb1=(a[i-1]*b[i]-a[i]*b[i-1])/gcd;ll tmpa2=gcd,tmpb2=b[i-1]*x+b[i]*y;a[i-1]=tmpa1,b[i-1]=tmpb1;a[i]=tmpa2,b[i]=tmpb2; }int nb=b[1];for (int i=2;icout<<0<<' '<" "<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！