1003b.cpp

平时acm训练时ac的源代码

#include <iostream> 
#include <cmath> 
using namespace std; 

const int MAX = 100; 
bool UsedBalloon[MAX+1]; 

bool CanFactor(int i, int b) 
{ 
if (b == 1) { 
return true; 
} else { 
while (i <= MAX) { // find a possible factor of b 
if ( (!UsedBalloon[i]) && ((b % i) == 0) ) { 
break; 
} else { 
i++; 
} 
} 
if (i > MAX) return false; 

// try the factor i 
if (CanFactor(i+1, b / i)) { 
return true; 
} else { 
// i can not be a factor 
return CanFactor(i + 1, b); 
} 
} 
} 

bool IsPossible(int i, int a, int b) 
{ 
if (i > MAX) return false; 
if (a == 1) return (CanFactor(1, b)); // try to factor b 

while (i <= MAX) { // find a possible factor of a 
if ((a % i) == 0) { 
break; 
} else { 
i++; 
} 
} 
if (i > MAX) return false; 
UsedBalloon[i] = true; 
if (IsPossible(i + 1, a / i, b)) return true; // try a factor i of a 
UsedBalloon[i] = false; 
return (IsPossible(i + 1, a, b)); // try not use i as factor of a 

} 

int GetWinner(int a, int b) 
{ 
for (int i = 0; i < MAX + 1; i++) { 
UsedBalloon[i] = false; 
} 

if (a < b) { // make sure b is the chanllenge 
int tmp = a; 
a = b; 
b = tmp; 
} 
if ((CanFactor(1, b) == false) && (b > 100)) { // chanllenge is lying. 
return a; 
} else if (IsPossible(1, a, b)) { // is it possible? 
return a; // chanllenge fail. 
} else { 
return b; // it's impossible, chanllenge win. 
} 
} 

int main() 
{ 
int a, b; 

while (cin >> a >> b) { 
cout << GetWinner(a, b) << endl; 
} 
return 0; 
}