HDOJ 5512 Pagodas 【2015沈阳现场赛】数论

在【1，n】中，给定两个数x，y，保证在范围内，而且不相等

新数产生的规则是：a+b，或者，a-b：也必须在区间内

问：最后是先手胜利（后手无法产生新数）还是后手胜利（先手无法产生新数）

数论的简单题：需要知道的结论是：as+bt=gcd（a，b）是一定找到s，t使得成立的

那么，就是看n中有多少个gcd（a，b）：数量为n/gcd（a，b）

其实分不分类都无所谓，只是分类好想一点

当a和b互质的时候，可以产生【1，n】中所有的数：新产生的数目为n-2：只需要判断奇偶

当a和b不互质的时候，我们需要单独特判：新产生的数目是多少？

然后，还是一样的判断奇偶就好了

#include<bits/stdc++.h>
using namespace std;

int t,n,a,b;

int gcd(int x,int y){
	if (x%y==0) return y;
	return gcd(y,x%y);
}

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d%d%d",&n,&a,&b);
		printf("Case #%d: ",Case);
		if (gcd(a,b)==1) n-=2;
		else{
			n/=gcd(a,b);
			if (gcd(a,b)==a||gcd(a,b)==b) n--;
			else n-=2;
		}
		if (n%2==0) puts("Iaka");
		else puts("Yuwgna");
	}
	return 0;
}