绝对值博弈时间限制1 秒空间限制256 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述Alice 和 Bob 在玩一款全新的关于绝对值的博弈游戏。给定一个包含n nn个不同整数的集合A AA双方轮流进行以下操作选择集合A AA中两个不同的整数x xx和y yy判定整数∣ 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≤1001 ≤ 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)ggcd(a1​,…,an​)的倍数。因此无论进行多少次“安全操作”集合中所有数始终是g gg的倍数且不会超过当前最大值m x max ⁡ a i mx\max a_imxmaxai​。最终满集若游戏一直进行而不立即输最终集合一定会包含所有在[ 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. 算法实现读入n nn和数组a aa。计算所有数的最大公约数g以及最大值mx。令need mx / g - n。若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的倍数。因此总安全操作次数是固定的胜负仅由该次数的奇偶性决定与玩家的具体选择无关。代码简要说明读入n nn初始化最大值mx0最大公约数ag0。遍历输入更新mx若ag仍为0 00将当前数字赋值给ag否则更新ag gcd(ag, num)。计算odd ((mx / ag - n) % 2 1)。根据odd输出Alice或Bob。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llgcd(ll a,ll b){ll x,y,tmp;if(ab){xa;yb;}else{xb;ya;}while(y){tmpx%y;xy;ytmp;}returnx;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cinn;ll mx0,ag0;for(ll i0;in;i){ll num;cinnum;if(nummx)mxnum;if(ag0)agnum;elseif(ag!1)aggcd(ag,num);}boolodd((mx/ag-n)%21);if(odd)coutAliceendl;elsecoutBobendl;return0;}