Rockdu's Blog

题目描述

欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：

Start：25 7

Stan：11 7

Ollie：4 7

Stan：4 3

Ollie：1 3

Stan：1 0

Stan赢得了游戏的胜利。

现在，假设他们完美地操作，谁会取得胜利呢？

输入输出格式

输入格式：

第一行为测试数据的组数C。下面有C行，每行为一组数据，包含两个正整数M, N。（M, N不超过长整型。）

输出格式：

对每组输入数据输出一行，如果Stan胜利，则输出“Stan wins”；否则输出“Ollie wins”

输入输出样例

2
25 7
24 15

Stan wins
Ollie wins​​

#include<cstdio>
#include<algorithm>
using namespace std;
int t, a, b;
bool gcd(int a, int b, bool now) {
	if(b == 0) return now;
	return a >= b << 1 ? now ^ 1 : gcd(b, a % b, now ^ 1);
}
int main() {
	scanf("%d", &t);
	for(register int i = 1; i <= t; ++i) {
		scanf("%d%d", &a, &b);
		if(a < b) swap(a, b);
		if(a == b) printf("Stan wins\n");
		else printf("%s\n", gcd(a, b, 0) ? "Stan wins" : "Ollie wins");
	}
	return 0;
}

短小精悍的SG函数233333:

#include<cstdio>
#include<algorithm>
#define For(i, a, b, c) for(register int i = a; i <= b; i += c)
#define N 25
using namespace std;
int sg[N + 5][N + 5];
void make(int n) {
	For(i, 1, n, 1) For(k, i, n, i)
		sg[i][k] = sg[k][i] = 1;
	For(i, 1, n, 1) For(j, 1, n, 1) for(int s = 1; ~s; swap(i, j), --s)
		if(!sg[i][j]) { For(k, i + j, n, j) sg[k][j] = 1;
						For(k, i + j, n, i) sg[i][k] = 1;}
}
int main() {
	make(N);
	For(i, 1, N, 1) { 
		For(j, 1, N, 1) printf("%d ", sg[i][j]);
		putchar('\n');
	}
}