Multiplication Game RMRC2017

5121: Multiplication Game

时间限制: 5 Sec   内存限制: 128 MB

提交: 157   解决: 32

[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

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≥2, and an integer M = 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 > N, the game is a tie.

Assuming that both players play optimally, who (if any) is going to win?

输入

The first line of input contains 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) followed by the name of the player making  the first turn. The name is either Alice or Bob.

输出

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

样例输入

 10

10 Alice

20 Bob

30 Alice

40 Bob

50 Alice

60 Bob

70 Alice

80 Bob

90 Alice

100 Bob

样例输出

Bob

Bob

tie

tie

Alice

tie

tie

tie

tie

Alice

思路：

1.任何合数都可以拆分成几个素数相乘的形式（最大到2的32次幂，那就以根号2的32次幂为界限，小于这个数的用素数筛扫一遍找素数，每次扫完都用米勒测试一下剩下的是不是素数，如果不是那接着扫23333）。

2.AB进行博弈的过程中，如果A发现自己一定会输，那A就会尝试让局面变成平局（tie）。

3.如果N由三种或以上的素数组成，必败的一方就可以让某一种素数被乘到超过原来应该乘的次数，从而导致平局。如果N由两种素数组成，并且两种素数的应该乘的次数差值大于等于2也会给必败的一方把局面变成平局的余地（比如一个数由4个2和2个3相乘得到，那么必败的一方总共可以操作(4+2)/2=3次，3次都乘3就可以变成平局。）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define LL long long
using namespace std;
 
 
LL prime[6] = {2,3,5,233,827};
LL qmul(LL x, LL y, LL mod)   // 乘法防止溢出， 如果p * p不爆LL的话可以直接乘； O(1)乘法或者转化成二进制加法
{
 
 
    return (x * y - (long long)(x / (long double)mod * y + 1e-3) *mod + mod) % mod;
    /*
    LL ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
        x = x * 2 % mod;
        y >>= 1;
    }
    return ret;
    //快速乘法*/
}
//快速乘
LL qpow(LL a, LL n, LL mod)
{
    LL ret = 1;
    while(n)
    {
        if(n & 1) ret = qmul(ret, a, mod);
        a = qmul(a, a, mod);
        n >>= 1;
    }
    return ret;
}
bool Miller_Rabin(LL p)
{
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    LL s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i)
    {
        if(p == prime[i]) return 1;
        LL t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1)
        {
            m = qmul(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}
 
//欧拉筛
const int maxn = 200000;
LL primee[maxn], notPrime[maxn], priCnt=0;
void getPrime()
{
    for (int i = 2; i < maxn; i++)
    {
        if (!notPrime[i])
            primee[priCnt++] = i;
        for (int j = 0; j < priCnt && i * primee[j] < maxn; j++)
        {
            notPrime[i * primee[j]] = 1;
            if (i % primee[j] == 0) break;
        }
    }
}
//对于1e18的数都有效
int main()
{
    int T;
    scanf("%d",&T);
    getPrime();
    while(T--)
    {
        long long n;
        long long pri[5]= {0}; //素因子
        long long side[5]= {0}; //每一个素因子出现的次数
        long long tot=0;//素因子的个数
        bool flag;
        char sidx[10];
        scanf("%lld",&n);
        scanf("%s",sidx);
        if(strcmp(sidx,"Alice")==0)
        {
            flag=true;
        }
        else
        {
            flag=false;
        }
        while(n!=1)
        {
            bool prr=false;
            for(int i=0; i<6800; i++)
            {
                if(n%primee[i]==0)
                {
                    prr=true;
                    bool chong=false;
                    for(int j=1; j<=tot; j++)
                    {
                        if(pri[j]==primee[i])
                        {
                            side[j]++;
                            chong=true;
                            break;
                        }
                    }
                    if(!chong)
                    {
                        tot++;
                        if(tot>2)
                        {
                            printf("tie\n");
                            goto endd;
                        }
                        else
                        {
                            pri[tot]=primee[i];
                            side[tot]++;
                        }
                    }
                    n=n/primee[i];
                }
            }
            if(!prr)
            {
                if(Miller_Rabin(n))
                {
                    bool chong=false;
                    for(int j=1; j<=tot; j++)
                    {
                        if(pri[j]==n)
                        {
                            side[j]++;
                            chong=true;
                            break;
                        }
                    }
                    if(!chong)
                    {
                        tot++;
                        if(tot>2)
                        {
                            printf("tie\n");
                            goto endd;
                        }
                        else
                        {
                            pri[tot]=n;
                            side[tot]++;
                        }
                    }
                    n=n/n;
                }
            }
 
        }
        bool ans;
        if(tot==1)
        {
            ans=side[1]%2;
        }
        else
        {
            if(abs(side[1]-side[2])>=2)
            {
                printf("tie\n");
                goto endd;
            }
            else
            {
                ans=(side[1]+side[2])%2;
            }
        }
        if((ans&&flag)||(!ans&&!flag))
        {
            printf("Alice\n");
        }
        else
        {
            printf("Bob\n");
        }
endd :
        ;
    }
    return 0;
}