zju1003.cpp

浙江大学acm第1003题解答

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

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

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

            // try the factor i 
        if (CanFactor(i+1, b / i))
        { 
            cout<<"CanFactor("<<i+1<<","<<b/i<<")=true,return true"<<endl;
            return true; 
        }
        else
        { 
            // i can not be a factor 
            cout<<" return CanFactor("<<i + 1<<", "<<b<<")"<<endl;
            return CanFactor(i + 1, b); 
        } 
    } 
} 
//first run IsPossible(1, a, b)
bool IsPossible(int i, int a, int b) 
{ 
    if (i > MAX) return false; 
    if (a == 1)
    {
        cout<<"a==1,return canfactor(1,b)"<<endl;
          return (CanFactor(1, b)); // try to factor b 
    }    
    while (i <= MAX) 
    { // find a possible factor of a 
        if ((a % i) == 0) 
        { 
            cout<<a<<"%"<<i<<"==0,break"<<endl;
            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) 
{ 
    cout<<" go to getWinner between "<<a<<"   and   "<<b<<endl;
    for (int i = 0; i < MAX + 1; i++)
    { 
        UsedBalloon[i] = false; //initial the UsedBallon
    } 

    if (a < b)
    { // make sure b is the chanllenge 
        cout<<" a<b, swap  and now "<<endl;
        int tmp = a; 
            a = b; 
            b = tmp; 
    } // make sure a is bigger than b  : a is nonofficial winner, b is chanllenge
       //a is the bigger number while b is the smaller
       cout<<"a="<<a<<"b="<<b<<endl;
    if ((CanFactor(1, b) == false) && (b > 100)) 
    { // chanllenge is lying. 
        cout<<"(CanFactor(1, "<<b<<") == false) && (b > 100), return a="<<a<<endl;
        return a; 
    } 
    else if (IsPossible(1, a, b))
    { // is it possible? 
        cout<<" IsPossible(1, "<<a<<", "<<b<<"), return a="<<a<<endl;
        return a; // chanllenge fail. 
    }
    else
    { 
        cout<<"return b="<<b<<endl;
        return b; // it's impossible, chanllenge win. 
    } 
} 

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