咨询：求解基于和积信息的猜数游戏问题的特定算法名称

问题背景 #

给定正整数n、x、y，玩家A知晓s = x + y，玩家B知晓p = x * y，两人轮流猜测x、y的具体值（要求x、y ≤ n）：

• 无法确定答案时，需说出“I don't know”，并统计该语句的出现次数
• 能确定答案时直接说出，游戏结束
• 存在无法猜出的情况，此时游戏会进入无限循环

核心算法：迭代式排除法 #

算法的核心逻辑是基于双方的公共知识（n的范围、对方每一轮的表态），逐步缩小可能的(x,y)数对范围，模拟两人的推理过程。

步骤1：初始化候选集合 #

先列出所有满足1 ≤ x ≤ y ≤ n的正整数对（避免重复，(x,y)与(y,x)视为同一解），记为总候选集S_total。

• 玩家A的初始候选集：A_curr = {(a,b) | a + b = s, 1 ≤ a ≤ b ≤ n}（所有和为s的数对）
• 玩家B的初始候选集：B_curr = {(a,b) | a * b = p, 1 ≤ a ≤ b ≤ n}（所有积为p的数对）

步骤2：轮流迭代推理（模拟游戏流程） #

游戏按「A→B→A→B...」的顺序进行，每一轮的推理都基于对方上一轮的表态，更新自己的候选集：

玩家A的回合

1. 若A_curr的大小为1：直接说出答案，游戏结束，统计当前累计的“I don't know”次数。
2. 若A_curr的大小>1：说出“I don't know”，次数+1。此时玩家B会知道「A的和s对应的数对不止一个」，因此B会更新自己的候选集：
   B_new = {(a,b) ∈ B_curr | 该数对的和s'满足：{(x,y)|x+y=s',1≤x≤y≤n}的大小>1}
   简单说：B会排除那些「如果自己拿到的积对应这个数对，A第一轮就应该能猜出答案」的数对。

玩家B的回合

1. 若B_curr的大小为1：直接说出答案，游戏结束，统计当前累计的“I don't know”次数。
2. 若B_curr的大小>1：说出“I don't know”，次数+1。此时玩家A会知道「B的积p对应的数对不止一个」，因此A会更新自己的候选集：
   A_new = {(a,b) ∈ A_curr | 该数对的积p'满足：{(x,y)|x*y=p',1≤x≤y≤n}的大小>1}
   简单说：A会排除那些「如果自己拿到的和对应这个数对，B第一轮就应该能猜出答案」的数对。

步骤3：终止条件 #

• 成功猜出：某一方的候选集缩小至1个，游戏结束，输出答案和统计的“I don't know”次数。
• 无限循环：连续两轮迭代后，A和B的候选集均未发生变化，说明无法通过进一步推理缩小范围，游戏终止。

示例验证 #

示例1：n=10，x=3，y=6（s=9，p=18） #

1. A初始候选集：{(1,8),(2,7),(3,6),(4,5)}（大小4>1）→ A说“I don't know”（次数=1）
2. B初始候选集：{(2,9),(3,6)}，检查两个数对的和：2+9=11（对应A候选集大小4>1）、3+6=9（对应A候选集大小4>1）→ B候选集仍为2个→ B说“I don't know”（次数=2）
3. A更新候选集：排除(2,7)（因为其积14对应的B候选集只有{(2,7)}，若A拿到的和是9且包含(2,7)，B第一轮就该猜出，所以B说不知道意味着这个数对不可能）→ A新候选集：{(1,8),(3,6),(4,5)}（大小3>1）→ A说“I don't know”（次数=3）
4. B更新候选集：检查(2,9)和(3,6)，(2,9)的和11对应的A候选集经过B第一轮排除后仍有多个数对，(3,6)的和9对应的A候选集也仍有多个→ B候选集还是2个→ B说“I don't know”（次数=4）
5. A再次更新候选集：排除(1,8)和(4,5)（它们的积对应的B候选集经过第二轮后，若A拿到的和是9包含这两个数对，B第二轮应该能猜出，但B说不知道，所以这两个数对被排除）→ A候选集只剩{(3,6)}→ A说出答案，游戏结束。

示例2：n=10，x=3，y=5（s=8，p=15） #

1. A初始候选集：{(1,7),(2,6),(3,5),(4,4)}（大小4>1）→ A说“I don't know”（次数=1）
2. B初始候选集经过A第一轮表态后，排除所有积对应的和能让A直接猜出的数对，最终仍保留多个可能；
3. A的候选集经过B第一轮表态后，同样保留多个可能；
4. 后续每一轮迭代，双方的候选集都不再缩小，因此游戏进入无限循环，无法猜出答案。

内容的提问来源于stack exchange，提问作者Đức Huy Hoàng