通过在数组中添加元素的成对差异来找到获胜者，直到在 Python 中成为可能

pythonserver side programmingprogramming更新于 2025/10/16 5:32:17

假设我们有一个由正整数组成的数组 A，元素是唯一的，现在，两个玩家 P 和 Q 正在玩游戏。每次移动时，任何一个玩家从数组中选择两个数字 a 和 b，如果 |a – b| 不在数组中，则玩家将此数字添加到数组中。当玩家无法移动时，游戏失败。如果玩家 P 总是开始游戏，我们必须找到游戏的赢家。

因此，如果输入为 A = [8,9,10]，则输出将为 P。

为了解决这个问题，我们将遵循以下步骤 −

n := arr 的大小
g := arr[0], max_val := arr[0]
对于范围从 1 到 n 的 i，执行
- g := gcd(g, arr[i])
- max_val := max_val 的最大值，arr[i]
total :=(max_val / g) - n
如果总数为奇数，则
- 返回"P"
返回"Q"

示例

让我们看看下面的实现以便更好地理解 −

from math import gcd
def who_is_the_winner(arr) :
   n = len(arr)
   g = arr[0]
   max_val = arr[0]
   for i in range(1, n) :
      g = gcd(g, arr[i])
      max_val = max(max_val, arr[i])
   total = (max_val / g) - n
   if (total % 2 == 1) :
      return 'P'
   return 'Q'

arr = [8,9,10]
print(who_is_the_winner(arr))