记录编号	343421	评测结果	AAAAAAAAAA
题目名称	Play with Power	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.458 s
提交时间	2016-11-09 10:23:29	内存使用	0.67 MiB

#include<cstdio>
#define file(x) "play."#x
typedef long long ll;
const int A = 10010,B = 40,INF=1<<30;
int n;
bool f[A][B];
bool ck(ll a,ll r){
	ll s = 1;
	while (r){
		if (r&1) s *= a;
		a *= a,r >>= 1;
		if (s > n) return 1;
	}
	return 0;
}
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	int T;
	scanf("%d%d",&n,&T);
	for (int i = A - 1;i;i--) for (int j = B - 1;j;j--) {
		if (ck(i,j + 1) && ck(i + 1,j)) f[i][j] = 0;
		else {
			f[i][j] = 0;
			if (!ck(i + 1,j)) f[i][j] |= !f[i + 1][j];
			if (!ck(i,j + 1)) f[i][j] |= !f[i][j + 1];
	 	}
	}
	while (T--) {
		int a,b;scanf("%d%d",&a,&b);
		if(ck(a,b + 1) && ck(a + 1,b)) printf("Stas\n");
		else if (a == 1 && ck(a + 1,b)) printf("Missing\n");
		else if (b == 1) printf("%s\n",(n-a)%2?"Masha":"Stas");
		else printf("%s\n",f[a][b]?"Masha":"Stas");
	}
}