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
1010 Alice20 Bob30 Alice40 Bob50 Alice60 Bob70 Alice80 Bob90 Alice100 Bob
Sample Output
BobBobtietieAlicetietietietieAlice 找到n的所有素因子 依次说出一个素数乘以M 看谁轮到谁的时候M==N 如果M>N 则平局 找规律当 素因子种类大于3个的时候， 其实可以在两个回合内预判对方能不能赢和自己能不能赢 双方都能够判断所以最好的结果只能是tie 当素因子种类为2时，当素因子个数差大于1的时候 是没有解的 这个考自己找规律 就是一个对称博弈 ，这个就是先后手的问题了 当种类数为1的时候 这个就非常显然了
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 const int maxn = 1e5+10;11 12 int vis[maxn], prime[maxn], k;13 int sum[1010] ;14 void init() {15 memset(vis, 0, sizeof(vis));16 k = 0;17 for (int i = 2 ; i < maxn ; i++ ) {18 if (vis[i]) continue;19 for (int j = 2 * i ; j < maxn ; j += i )20 vis[j] = 1;21 vis[i] = 1;22 prime[k++] = i;23 }24 }25 int main() {26 int t;27 init();28 scanf("%d", &t);29 while(t--) {30 int n, tot = 0, m;31 char name[100];32 memset(sum, 0, sizeof(sum));33 scanf("%d%s", &n, name);34 m = n;35 for (int i = 0 ; i < k && prime[i]*prime[i] <= m ; i++) {36 if (m % prime[i] == 0) {37 while(m % prime[i] == 0) {38 sum[tot]++;39 m = m / prime[i];40 }41 tot++;42 }43 }44 if (m != 1) {45 sum[tot]++;46 tot++;47 }48 if (tot >= 3) printf("tie\n");49 else if(tot == 2) {50 int temp = abs(sum[0] - sum[1]);51 if (temp == 0) printf("%s\n", (name[0] == 'A') ? "Bob" : "Alice");52 else if (temp == 1) printf("%s\n", (name[0] == 'B') ? "Bob" : "Alice");53 else printf("tie\n");54 } else if (tot == 1) {55 if (sum[0] & 1) printf("%s\n", (name[0] == 'B') ? "Bob" : "Alice");56 else printf("%s\n", (name[0] == 'A') ? "Bob" : "Alice");57 }58 }59 return 0;60 }