- 给定马的(n)种走法((a_i,b_i))（可以选择将横纵坐标同时加/减(a_i,b_i)）。
- 要求你给出两种走法，使得仅通过这两种走法能到达的所有位置与原先相同。
- (nle100)
走法的合并
先考虑如何合并两种走法((a,b),(c,d))。
首先要知道一个结论：肯定存在一种构造方案，使得最终的两种走法中存在至少一种是竖直的（也可以说至少一种是水平的，看个人喜好）。
要让能到达的位置相同，首先必须满足能到达的横坐标完全相同，而我们选取了一种走法是竖直的，另一种就必须要满足能够到达所有横坐标。
因此我们通过(exgcd)求出(ap+cq=gcd(a,c))的一组解，则这非竖直走法可以构造成((ap+cq,bp+dq))，不妨记作((A,B))。
而竖直走法就考虑仅通过((A,B))分别走到(x=a,x=c)时所需的调整，应该是((0,gcd(b-frac aA imes B,d-frac cA imes B)))。
一次合并得到了一种非竖直走法和一种竖直走法，非竖直走法直接扔回去继续搞（相当于一次操作减少了一种非竖直走法），而多种竖直走法的合并只要给第二维取(gcd)即可，非常容易。
代码：(O(nlogV))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100
using namespace std;
int n,a[N+5],b[N+5];I int gcd(CI x,CI y) {return y?gcd(y,x%y):x;}
I void exgcd(CI x,CI y,int& a,int& b) {y?(exgcd(y,x%y,b,a),b-=x/y*a):(a=1,b=0);}
int main()
{
RI i;for(scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",a+i,b+i);
RI p,q,A,B,t=0;for(i=2;i<=n;++i) exgcd(a[i-1],a[i],p,q),//exgcd求出一组解
A=a[i-1]*p+a[i]*q,B=b[i-1]*p+b[i]*q,t=gcd(t,gcd(b[i-1]-a[i-1]/A*B,b[i]-a[i]/A*B)),a[i]=A,b[i]=B;//更新非竖直走法，竖直走法第二维取gcd
return printf("0 %d
%d %d
",t,a[n],b[n]),0;
}