企业官网建设流程全解析

绝对值博弈

时间限制：1 秒
空间限制：256 MB

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

Alice 和 Bob 在玩一款全新的关于绝对值的博弈游戏。

给定一个包含n nn个不同整数的集合A AA，双方轮流进行以下操作：

1. 选择集合A AA中两个不同的整数x xx和y yy；
2. 判定整数∣ x − y ∣ |x - y|∣x−y∣：
   • 若∣ x − y ∣ |x - y|∣x−y∣也在集合A AA中，则执行此次操作的玩家立刻输掉这场游戏；
   • 若∣ x − y ∣ |x - y|∣x−y∣不在集合A AA中，则将整数∣ x − y ∣ |x - y|∣x−y∣插入到集合A AA中，随后交替到对方操作。

Alice 想知道，如果自己先手，且自己和 Bob 都采取最优策略，最终谁能获胜？

输入描述

第一行包含一个整数n ( 2 ≤ n ≤ 100 ) n\ (2 \le n \le 100)n(2≤n≤100)，表示集合中初始元素的数量。

第二行包含n nn个不同的空格分隔的整数a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 10 9 ) a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)a1​,a2​,…,an​(1≤ai​≤109)，表示集合中的元素。

输出描述

如果 Alice 在最优策略下能够赢得游戏，请输出Alice；否则输出Bob。

示例

示例 1

输入：

2 2 3

输出：

Alice

数据范围与提示

• 2 ≤ n ≤ 100 2 \le n \le 1002≤n≤100
• 1 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109
• 集合A AA中的元素互不相同。
• 该游戏属于组合博弈问题，可以考虑使用 SG 函数、必胜/必败态分析或记忆化搜索等方法求解。

解题思路

本题是组合博弈 + 数论性质的题型。表面上双方每次选择两个数做差，但博弈的胜负其实由初始集合的最大公约数决定，可以转化为确定步数的取石子游戏。

1. 问题等价转化

• 差操作保持 gcd 不变：对集合中任意两个数x , y x,yx,y，它们的差∣ x − y ∣ |x-y|∣x−y∣仍然是原来所有数的最大公约数g = gcd ⁡ ( a 1 , … , a n ) g=\gcd(a_1,\dots,a_n)g=gcd(a1​,…,an​)的倍数。因此无论进行多少次“安全操作”，集合中所有数始终是g gg的倍数，且不会超过当前最大值m x = max ⁡ a i mx=\max a_imx=maxai​。
• 最终满集：若游戏一直进行而不立即输，最终集合一定会包含所有在[ g , m x ] [g,\ mx][g,mx]范围内且是g gg的倍数的数。这样的数共有
  m x g \ \frac{mx}{g} \gmx​
  个。因为若还没满，总能找到某个缺失的g gg的倍数，并选择两个数使其差等于该值，从而进行一次安全操作。所以玩家无法改变总安全操作次数。
• 安全操作次数固定：
  初始集合已有n nn个数，因此从初始到满集还需要补入
  m x g − n \ \frac{mx}{g}-n \gmx​−n
  个不同的g gg的倍数。每次安全操作恰好补入一个，所以总安全操作次数就是m x g − n \frac{mx}{g}-ngmx​−n。
• 胜负判定：
  • 当补入全部数后，任意两个数的差一定在集合中，此时轮到谁操作谁输。
  • 因此胜负只取决于m x g − n \frac{mx}{g}-ngmx​−n的奇偶性：
    • 若为奇数，Alice 先手执行最后一次安全操作，Bob 面对死局，Alice 胜；
    • 若为偶数，Bob 执行最后一次安全操作，Alice 面对死局，Bob 胜。

2. 算法实现

1. 读入n nn和数组a aa。
2. 计算所有数的最大公约数g，以及最大值mx。
3. 令need = mx / g - n。
4. 若need为奇数，输出Alice；否则输出Bob。

3. 复杂度分析

• 时间复杂度：计算 gcd 和最大值只需一次遍历，复杂度O ( n log ⁡ max ⁡ a i ) O(n \log \max a_i)O(nlogmaxai​)。
• 空间复杂度：O ( 1 ) O(1)O(1)，仅需常数变量。

总结

游戏过程可以被抽象为固定长度的“安全补数”过程：所有操作均保持 gcd 不变，最终集合必然扩展为[ g , m x ] [g, mx][g,mx]内所有g gg的倍数。因此总安全操作次数是固定的，胜负仅由该次数的奇偶性决定，与玩家的具体选择无关。

代码简要说明

1. 读入n nn，初始化最大值mx=0，最大公约数ag=0。
2. 遍历输入：
   • 更新mx；
   • 若ag仍为0 00，将当前数字赋值给ag；
   • 否则更新ag = gcd(ag, num)。
3. 计算odd = ((mx / ag - n) % 2 == 1)。
4. 根据odd输出Alice或Bob。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llgcd(ll a,ll b){ll x,y,tmp;if(a>b){x=a;y=b;}else{x=b;y=a;}while(y){tmp=x%y;x=y;y=tmp;}returnx;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;ll mx=0,ag=0;for(ll i=0;i<n;i++){ll num;cin>>num;if(num>mx)mx=num;if(ag==0)ag=num;elseif(ag!=1)ag=gcd(ag,num);}boolodd=((mx/ag-n)%2==1);if(odd)cout<<"Alice"<<endl;elsecout<<"Bob"<<endl;return0;}