1. 题目分析

问题描述

Gizilch游戏判定规则：

1. 两玩家分别报告分数$A$和$B$（$A \neq B$）
2. 判定逻辑：
   • 若$A$和$B$均可由$[2,100]$内不重复数字的乘积表示且无冲突 → 高分者胜
   • 若低分者$B$无法被表示 → 高分者$A$胜
   • 若高分者$A$无法被表示或与$B$冲突 → 低分者$B$胜

输入输出

• 输入：多组$A\ B$（$A,B \geq 1$）
• 输出：每组对应的胜者分数

2. 解题思路

核心算法

1. 合法性检查（find函数）：

   • 递归检查分数$x$是否能分解为$[2,100]$内不重复数的乘积
   • 数学表达：$$\text{find}(x,cur) = \begin{cases} \text{false} & \text{if } x=1 \\ \text{find}(x,cur+1) & \text{if } cur \nmid x \\ \text{find}(\frac{x}{cur},cur+1) \land \text{find}(x,cur+1) & \text{if } cur \mid x \end{cases} $$

2. 冲突检查（judge函数）：

   • 递归检查两分数是否共用相同数字
   • 数学表达：$$\text{judge}(A,B,cur) = \begin{cases} \text{false} & \text{if } A=B=1 \\ \bigwedge_{d \mid A \lor d \mid B} \text{judge}(\frac{A}{d}, \frac{B}{d}, cur+1) & \text{otherwise} \end{cases} $$

3. 复杂度分析

• 时间复杂度：
  • 最坏情况$O(2^{100})$（递归树深度）
  • 实际因剪枝远低于理论值
• 空间复杂度：$O(100)$（递归栈深度）

4. 代码实现

#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#define maxn 100
 
 
/*
 * 判断a是否合题意
 * a是否是可能出现的
 * a不可能出现则返回1
 */
bool find(int a, int cur)
{
	if (a == 1) return false;
	if (cur > 100) return true;
	int tmp = find(a, cur + 1);
	if (a % cur == 0)
		return find(a / cur, cur + 1) && tmp;
	return tmp;
}
 
/*如果发现冲突则返回1*/
bool judge(int a, int b, int cur)
{
	if (a == 1 && b == 1) return false;
	if (cur > 100) return true;
	int mod_a = a % cur, mod_b = b % cur;
	int tmp1 = 0, tmp2 = 0, tmp3 = 0;
	if (!mod_a) tmp1 = judge(a / cur, b, cur + 1);
	if (!mod_b) tmp2 = judge(a, b / cur, cur + 1);
	tmp3 = judge(a, b, cur + 1);
	if (!mod_a && !mod_b)
	{
		return tmp1 && tmp2 && tmp3;
	}
 
	if (!mod_a)
		return tmp1 && tmp3;
	if (!mod_b)
		return tmp2 && tmp3;
	return tmp3;
}
 
 
int main()
{
	int m = 0, n = 0;
	while (scanf("%d%d", &m, &n) != EOF)
	{
 
		if(m < n)/*keep m >= n*/
		{
			int tmp = m;
			m = n;
			n = tmp;
		}
 
		int tmp1 = find(m, 2);
		int tmp2 = find(n, 2);
		int tmp3 = judge(m, n, 2);
		if (!(tmp1 || tmp2 || tmp3))/*m,n两数均合法,输出大者*/
			printf("%d\n", m);
		else if(tmp2)/*若小者不合法,直接输出大者*/
			printf("%d\n", m);
		else printf("%d\n", n);/*否则输出小者*/
		
	}
	return 0;
}