AtCoder Grand Contest 010 D - Decrementing
2024-10-10 21:24:43
题目描述
有n个整数,其中第i个数为Ai。这些数字的gcd为1。两人轮流操作,每次操作把一个大于1的数减1,并把所有数除以所有数的最大公约数,最后无法操作者输,求是否先手必胜。
如果当前的sum为偶数,那么减一之后sum变为奇数,gcd必为奇数,而任意数除一个奇数后奇偶性不变,故这步走完后sum必然为奇数。
如果当前的sum为奇数,减一之后sum变为偶数,如果当前全为偶数,那么除完gcd后奇偶不一定,否则sum依然为偶数。
当局面全为1的时候先手必败,此时的奇偶为$n%2$,考虑先手怎样控制局面取得胜利。
假设先手的局面$sum\%2!=n\%2$,那么先手一定必胜,后手改变局面的唯一机会是使减完后gcd为2的倍数,则n个数都%2后必须只有一个1,先手只要每回把一个0变成1后手就无法翻盘。
那如果$sum\%2=n\%2$,如果满足n个数%2后只有一个1且先手必须要把1变0先手才可能赢,否则必败。
模拟一下过程,gcd为2的倍数的次数最多log次。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[];
ll sum=;
void print(int x)
{
if(!x)puts("First");
else puts("Second");
}
int gcd(int x,int y)
{
if(!y)return x;
return gcd(y,x%y);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);sum+=a[i];
}
int now=;
while()
{
if(n%!=sum%)return print(now),;
int id=;
for(int i=;i<=n;i++)
{
if(a[i]%==&&a[i]!=)
{
if(!id)id=i;
else return print(now^),;
}
}
if(!id)return print(now^),;
a[id]--;
int g=a[];for(int i=;i<=n;i++)g=gcd(g,a[i]);
sum=;
for(int i=;i<=n;i++)a[i]/=g,sum+=a[i];
now^=;
}
return ;
}
最新文章
- ManagementClass类解析和C#如何获取硬件的相关信息
- IOS开发基础知识--碎片34
- SCRIPT5011:不能执行已释放Script的代码
- java.net.UnknownHostException: promote.cache-dns.local: unknown error
- 20145301&;20145321&;20145335实验四
- ContentProvider详解
- As.net WebAPI CORS, 开启跨源访问,解决错误No &#39;Access-Control-Allow-Origin&#39; header is present on the requested resource
- Dubbo认识
- 如何使用VSTS做压力测试
- 华为oj - 统计大写字母个数
- vertical-align 与 line-height 傻傻分不清??
- shell 运算符章节笔记
- Chapter 5 Blood Type——7
- (转)通过注册表修改VC6.0的字体
- python3下调用系统massagebox对话框
- Fundebug是这样备份数据的
- gcc/g++ disable warnings in particular include files
- vm虚拟机黑屏解决办法
- docker samba
- 图形化调试工具DDD