题目链接:https://codeforces.com/problemset/problem/346/A
题目大意:给你一个数组,有n个不同的数。然后小A和小B轮流玩游戏,找出两个数的绝对值的差|x-y|,如果数组中不存在这个数的话,就把这个数添加到数组中;如果实在找不出来两个数的差,既|x-y|,总是在数组中存在,那么这个同学就输了。
举个例子。比如,数组元素是1,3。那么第一个同学,只能将|3-1|为2存进去。这个时候数组就是1,2,3。此时,任何两个数的差的绝对值都在数组里,所以第一个同学就赢了。
如果多举几个例子,很容易发现一个规律,如果两个数啊a,b互质的话,那么就可以构造出1~max(a,b)所有的数,先假设这个规律是正确的,暂时还不会证明0.0,但是感觉吧一定是对的0.0。
举个例子:
比如 3,11;
然后是3,8,11;
然后是3,5,8,11;
然后是2,3,5,8,11;
然后是1,2,3,5,8,11。
如果有了1,就可以把1到11所有的数构造出来了。
还能得到一个结论,如果一开始数组中存在任意两组数a,b互质的话,如果数组中还有c>=max(a,b),那么1~c所有的整数都可以构造出来,因为只要有1,那么1到一个数之间所有的数都可以都早出来。
再进一步,就可以推到本题的答案,如果数组中存在一组(a,b)互质,那么之需要判断,(数组中最大的数max-数组个数n)的是奇数还是偶数就可以了。
如果数组中任意一组(a,b)都不互质,那么可以可以求出数组所有的元素的最大公约数,约掉后,数组中就存在互质对了,然后就可以按照上一步做了。
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn =101;
int num[maxn];
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n,flag;
while(cin>>n)
{
flag=1;
for(int i=0;i<n;i++)
{
cin>>num[i];
}
sort(num,num+n);
for(int i=0;i<n-1;i++) //判断是否有互质对
{
for(int j=i+1;j<n;j++)
{
if(gcd(num[i],num[j])==1)
{
flag=0;
}
}
}
int ans=0;
if(!flag){ //有的话,直接判断ans的奇偶性
ans=num[n-1]-n;
}else //没有的话,用res寻找所有的元素的最大公约数
{
int res=gcd(num[0],num[1]);
for(int i=2;i<n;i++)
{
if(res>gcd(res,num[i]))
{
res=gcd(res,num[i]);
}
}
ans=(num[n-1]/res)-n; //实际上把最大的数化简就可以了
}
if(ans&1)
{
cout<<"Alice"<<endl;
}else
{
cout<<"Bob"<<endl;
}
}
return 0;
}turn 0;
}
3 comments
嗯嗯,有啥问题尽管问,大家一起学习233