Multiplication Game

Description

Alice and Bob are in their class doing drills on multiplication and division. They quickly get bored and instead decide to play a game they invented.

The game starts with a target integer N≥2N≥2 , and an integer M=1M=1. Alice and Bob take alternate turns. At each turn, the player chooses a prime divisor p of N, and multiply M by p. If the player’s move makes the value of M equal to the target N, the player wins. If M>NM>N , the game is a tie. Assuming that both players play optimally, who (if any) is going to win?

Input

The first line of input contains T(1≤T≤10000)T(1≤T≤10000) , the number of cases to follow. Each of the next T lines describe a case. Each case is specified by N(2≤N≤231−1)N(2≤N≤231−1) followed by the name of the player making the first turn. The name is either Alice or Bob.

Output

For each case, print the name of the winner (Alice or Bob) assuming optimal play, or tie if there is no winner.

Sample Input

10

10 Alice

20 Bob

30 Alice

40 Bob

50 Alice

60 Bob

70 Alice

80 Bob

90 Alice

100 Bob

Sample Output

Bob

Bob

tie

tie

Alice

tie

tie

tie

tie

Alice

Hint

博弈论；质因数分为一种，两种，和多种，多种必平局，一种时，该质因数数量为奇数时，第一个人胜，偶数则第二个人胜；

两种时，若两种数量相同，则第二个人胜，若相差一个，则第一个胜，否则平局。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

const int mod = 1e9+7;

typedef long long ll;

const int maxn = 1e5+100;

int prime[maxn+10];

bool vis[maxn];

ll cnt;

void judge(int n)

{

    cnt=0;

    vis[1]=true;

    ll i,j;

    for(i=2; i<=n; i++)

    {

        if(!vis[i])

        {

            prime[cnt++]=i;

        }

        for(j=0; j<cnt && i*prime[j] <= n; j++)

        {

            vis[i*prime[j]]=true;

            if(i%prime[j]==0) break;

        }

    }

}

int main()

{

    judge(maxn);

    int T;

    cin>>T;

    while(T--)

    {

        ll n;

        string ss;

        cin>>n>>ss;

        int ret = 0;

        vector<int> v;

        for(int i=0; i<cnt; i++)

        {

            if(n%prime[i]==0)

            {

                ret++;

                int tmp=0;

                while(n%prime[i]==0)

                {

                    n/=prime[i];

                    tmp++;

                }

                v.push_back(tmp);

            }

            if(ret>=3) break;

        }

        if(n>1)

        {

            ret++;

            v.push_back(1);

        }

        if(ret>=3) cout<<"tie"<<endl;

        else if(ret==1)

        {

            if(v[0]%2==0)

            {

                if(ss=="Alice") cout<<"Bob"<<endl;

                else cout<<"Alice"<<endl;

            }

            else

            {

                if(ss!="Alice") cout<<"Bob"<<endl;

                else cout<<"Alice"<<endl;

            }

        }

        else if(ret==2)

        {

            if(v[1]==v[0])

            {

                if(ss=="Alice") cout<<"Bob"<<endl;

                else cout<<"Alice"<<endl;

            }

            else

            {

                if(abs(v[0]-v[1])==1)

                {

                	if(ss!="Alice") cout<<"Bob"<<endl;

                    else cout<<"Alice"<<endl;

				}

                else cout<<"tie"<<endl;

            }

        }

        else cout<<ss<<endl;

    }

 	return 0;

}

/**********************************************************************

	Problem: 2115

	User: song_hai_lei

	Language: C++

	Result: AC

	Time:1456 ms

	Memory:2512 kb

**********************************************************************/

巴特西