前言

填一個月前的坑，這次比賽的題目質量很高，我到現在才改完，

題目

https://gmoj.net/senior/#main/show/3983

題解

題目大意是給你一個網格圖，你可以以任意一點為中心進行任意次“十字變換”或“X型變換”，接著有T個詢問，每次問你能否通過變換把(x,y)弄到(0,0)，

比賽時考慮把X型變換全部變成十字變換，然而這其實并沒有用，

題目給的這個L是包括了變換中心的，可以把它去掉，令 l = L ? 1 l=L-1 l=L?1，
發現對于一個坐標 ( x , y ) (x,y) (x,y)，可以進行如下操作（ 1 ≤ i ≤ l 1\leq i\leq l 1≤i≤l）：

1. ( x ± i , y ± i ) (x\pm i,y\pm i) (x±i,y±i)
2. ( x ± 2 i , y ) (x\pm 2i,y) (x±2i,y)
3. ( x , y ± 2 i ) (x,y\pm 2i) (x,y±2i)

因為不同象限的點的走法是一樣的，為了方便處理，可以把每個點都翻折到第一象限中，
看到如上的走法，不難發現，若x和y的奇偶性不同，那么無法到達，
還有一個重要的性質：斜著走最多只會走兩次，
這里給出證明（不妨把斜著走的那幾步都平移在起來，假設 ( x , y ) (x,y) (x,y)連續斜著走了3次后變成 ( x ? s t e p , y ? s t e p ) (x-step,y-step) (x?step,y?step)）

如果 s t e p ≤ 2 l step\leq 2l step≤2l，那么不如斜著走2步優；
如果 s t e p > 2 l step>2l step>2l，那么前 2 l 2l 2l的路程可以通過操作2、3得到，

并且可以發現，如果斜著走了2步，當且僅當step是奇數，

然后下面就是貪心處理環節了（說真的，這題的貪心很難想到，要考慮的情況很多），不妨設x≥y，反之將x和y交換即可：

• 如果x+y是奇數，無解；
• 把(x,y)移動到較小的范圍，于是分別橫著走、豎著走，變成 ( x m o d ?? 2 l , y m o d ?? 2 l ) (x\mod 2l,y\mod 2l) (xmod2l,ymod2l)（記為 ( x ′ , y ′ ) (x',y') (x′,y′)），令 a n s 1 = ? x 2 l ? + ? y 2 l ? ans1=\left\lfloor\cfrac{x}{2l}\right\rfloor+\left\lfloor\cfrac{y}{2l}\right\rfloor ans1=?2lx??+?2ly??，
• 下面再進行分類討論：
  • 如果 y ≥ 2 l y\geq 2l y≥2l，那么可以讓x’或y’中的較小者最后一步少跳一點，使得兩者都變成較大值，從而用操作1解決問題， a n s 2 = ? max ? ( x ′ , y ′ ) l ? ans2=\left\lfloor\cfrac{\max(x',y')}{l}\right\rfloor ans2=?lmax(x′,y′)??；
  • 如果 x ≥ 2 l , 且 x ′ ≤ y < 2 l x\geq 2l,且x'\leq y<2l x≥2l,且x′≤y<2l，那么可以讓x’最后一步少跳一點，使得x’=y，再用操作1解決問題， a n s 2 = ? y l ? ans2=\left\lfloor\frac{y}{l}\right\rfloor ans2=?ly??；
  • 考慮任意的 ( x ′ , y ′ ) (x',y') (x′,y′)怎么跳，不妨設x‘≥y’，反之將x‘和y’交換即可，如果 y ′ ≥ l y'\geq l y′≥l，那么x‘和y’減去l，同時ans2加上1（下同），接著再同時跳y‘步，此時坐標為 ( x ′ ? y ′ , 0 ) (x'-y',0) (x′?y′,0)，如果此時x‘變成了奇數，就將它+1變回偶數（這只是第一次少跳一步而已，不是新的操作，目的是方便接下來的處理），再用一次操作2解決問題，
  • 還有一種走法： a n s 2 = [ x ′ > 0 ] + [ y ′ > 0 ] + [ 2 ∣? x ′ ] ans2=[x'>0]+[y'>0]+[2\not|x'] ans2=[x′>0]+[y′>0]+[2?∣x′]，

這題最惡心的就是高精度運算了，好在可以不壓位，

CODE

#include<cstdio>
#include<cstring>
using namespace std;
#define P 100000000
#define N 505
int tmp[N];
inline char gc()
{
	static char buf[100005],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;
}
struct bignum
{
	long long a[N];int len;
	bignum(){memset(a,0,sizeof a),len=1;}
	inline void clear(){memset(a,0,sizeof a),len=1;}
	inline void read()
	{
		char ch;int cnt=1;
		memset(a,0,sizeof a);
		while(ch=gc(),ch<'0'||ch>'9');tmp[1]=ch-'0';
		while(ch=gc(),ch>='0'&&ch<='9') tmp[++cnt]=ch-'0';
		len=cnt>>3;if(len<<3<cnt) ++len;
		for(int i=cnt,k=1;k<=len;i-=8,++k)
			for(int j=7;j>=0;--j) if(i>j) a[k]=a[k]*10+tmp[i-j];
	}
	inline void print()
	{
		printf("%lld",a[len]);
		for(int i=len-1;i;--i) printf("%08lld",a[i]);
		putchar('\n');
	}
}_1,_0,re,inf;//re是余數
inline int mymax(int x,int y){return x>y?x:y;}
inline bignum move(bignum x)
{
	if(x.len==1&&!x.a[1]) return x;
	for(int i=x.len;i;--i) x.a[i+1]=x.a[i];
	++x.len,x.a[1]=0;
	return x;
}
inline bool judge(bignum x,bignum y) // x>y
{
	if(x.len^y.len) return x.len>y.len;
	for(int i=x.len;i;--i)
		if(x.a[i]^y.a[i]) return x.a[i]>y.a[i];
	return 0;
}
inline bignum plus(bignum x,bignum y)
{
	bignum z;
	z.len=mymax(x.len,y.len);
	for(int i=1;i<=z.len;++i)
	{
		z.a[i]=x.a[i]+y.a[i];
		if(z.a[i]>=P) z.a[i]-=P,++x.a[i+1];
	}
	if(z.a[z.len+1]) ++z.len;
	return z;
}
inline bignum plus(bignum x,int y)
{
	x.a[1]+=y;
	for(int i=1;i<=x.len&&x.a[i]>=P;++i)
		++x.a[i+1],x.a[i]-=P;
	if(x.a[x.len+1]) ++x.len;
	return x;
}
inline bignum minus(bignum x,bignum y)
{
	for(int i=1;i<=x.len;++i)
	{
		x.a[i]-=y.a[i];
		if(x.a[i]<0) x.a[i]+=P,--x.a[i+1];
	}
	while(x.len>1&&!x.a[x.len]) --x.len;
	return x;
}
inline bignum times(bignum x,int y)
{
	if(!y) return _0;
	bignum z;z.len=x.len;
	for(int i=1;i<=x.len;++i)
	{
		z.a[i]+=x.a[i]*y;
		z.a[i+1]+=z.a[i]/P;
		z.a[i]%=P;
	}
	while(z.a[z.len+1])
	{
		++z.len;
		z.a[z.len+1]+=z.a[z.len]/P;
		z.a[z.len]%=P;
	}
	return z;
}
inline bignum div(bignum x,bignum y) // ceil(x/y)
{
	bignum z;
	z.len=x.len,re.clear();
	for(int i=z.len,l,r,mid,num;i;--i)
	{
		re=plus(move(re),x.a[i]);
		l=num=0,r=P-1;
		while(l<=r)
		{
			mid=l+r>>1;
			if(judge(times(y,mid),re)) r=mid-1;
			else l=mid+1,num=mid;
		}
		re=minus(re,times(y,num));
		z.a[i]=num;
	}
	while(z.len>1&&!z.a[z.len]) --z.len;
	return z;
}
inline bignum max(bignum x,bignum y){return judge(x,y)?x:y;}
inline bignum min(bignum x,bignum y){return judge(y,x)?x:y;}
inline int calc(bignum x,bignum y,bignum l) // (x,y)->(0,0) y<=x<2l
{
	int s=0;
	if(!judge(l,y)) x=minus(x,l),y=minus(y,l),++s;
	if(!judge(x,_0)) return s;
	if(x.a[1]&1) x=plus(x,1),y=plus(y,1);
	x=minus(x,y),++s;
	return s+judge(x,_0);
}
int main()
{
	bignum ans1,ans2,x,y,l,_2l,xx,yy,z;
	int t;_1.a[1]=1;
	scanf("%d",&t);
	inf.len=500;for(int i=1;i<501;++i) inf.a[i]=P-1;
	while(t--)
	{
		x.read(),y.read(),l.read();
		if(judge(y,x)) z=x,x=y,y=z;
		if(x.a[1]+y.a[1]&1) puts("Poor MLG!");
		else
		{
			l=minus(l,_1);
			_2l=times(l,2);
			ans1=div(x,_2l),xx=re;
			ans1=plus(ans1,div(y,_2l)),yy=re;
			if(judge(yy,xx)) z=xx,xx=yy,yy=z;
			if(!judge(_2l,y)) ans2=div(xx,l),ans2=plus(ans2,judge(re,_0));
			else if((!judge(_2l,x))&&!judge(xx,y)) ans2=div(y,l),ans2=plus(ans2,judge(re,_0));
			else ans2=inf;
			ans2=min(min(ans2,plus(_0,calc(xx,yy,l))),plus(_0,judge(xx,_0)+(int)judge(yy,_0)+((xx.a[1]&1)?1:0)));
			ans1=plus(ans1,ans2),ans1.print();
		}
	}
	return 0;
}