踩气球

时限：1000ms 内存限制：10000K 总时限：3000ms

描述：

六一儿童节，小朋友们做踩气球游戏，气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。

输入：

输入为两个数字，0 0表示结束；

输出：

输出为获胜的数字。

输入样例：

36 62

49 343

0 0

输出样例：

62

49

code：

#include <iostream>

using namespace std;

int flag1 = 0,flag2 = 0;

void dfs(int a,int b,int k)
{
	if(b == 1)
	{
		flag2 = 1;
		if(a == 1)
		{
			flag1 = 1;
		}
	}
	if(k == 1||(flag1&&flag2))
		return;
	if(a % k == 0)
		dfs(a/k,b,k-1);
	if(b % k == 0)
		dfs(a,b/k,k-1);
	dfs(a,b,k-1);
}
int main()
{
	int num1,num2;
	while(cin >> num1 >> num2)
	{
		if(num1 == 0&&num2 == 0)
			break;
		if(num1 < num2)
		{
			int t = num1;
			num1 = num2;
			num2 = t;
		}
		flag1 = flag2 = 0;
		dfs(num1,num2,100);
		if(!flag1 && flag2)
			cout << num2 << endl;
		else
			cout << num1 << endl;
	}
	return 0;
}

首先判断数字小的是否是真，如果是，再判断数字大的是否是真；如果数字小的是假，则数字大的赢。