ACdream 1112
9437 ワード
タイトルリンク
Alice and Bob
Time Limit: 6000/3000MS (Java/Others)Memory Limit: 256000/128000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
Here is Alice and Bob again !
Alice and Bob are playing a game. There are several numbers.First, Alice choose a number n.Then he can replace n (n > 1)with one of its positive factor but not itself or he can replace n with a and b.Here a*b = n and a > 1 and b > 1.For example, Alice can replace 6 with 2 or 3 or (2, 3).But he can’t replace 6 with 6 or (1, 6). But you can replace 6 with 1. After Alice’s turn, it’s Bob’s turn.Alice and Bob take turns to do so.Who can’t do any replace lose the game.
Alice and Bob are both clever enough. Who is the winner?
Input
This problem contains multiple test cases. The first line contains one number n(1 <= n <= 100000).
The second line contains n numbers.
All the numbers are positive and less than of equal to 5000000.
Output
For each test case, if Alice can win, output “Alice”, otherwise output “Bob”.
Sample Input
Sample Output
Source
yehuijie
Manager
wuyiqi
n個の数を与え、2つの順番に任意の数nを選択して操作し、第1の操作はこの数を彼の因子に変えることであるが、それ自体に変えることはできない.
2つ目は、a*b=nを満たす2つの数aとbになります.ａ>1, b>1.
初めて線形ふるいを書くと、このアルゴリズムは普通のふるい法とは少し違いますが、もっと理解しにくいです.つまり、アルゴリズムは数ごとに
彼の最小の質因子はふるいにかけた.アルゴリズムの時間が線形であることも保証されている.
Accepted Code:
Alice and Bob
Time Limit: 6000/3000MS (Java/Others)Memory Limit: 256000/128000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
Here is Alice and Bob again !
Alice and Bob are playing a game. There are several numbers.First, Alice choose a number n.Then he can replace n (n > 1)with one of its positive factor but not itself or he can replace n with a and b.Here a*b = n and a > 1 and b > 1.For example, Alice can replace 6 with 2 or 3 or (2, 3).But he can’t replace 6 with 6 or (1, 6). But you can replace 6 with 1. After Alice’s turn, it’s Bob’s turn.Alice and Bob take turns to do so.Who can’t do any replace lose the game.
Alice and Bob are both clever enough. Who is the winner?
Input
This problem contains multiple test cases. The first line contains one number n(1 <= n <= 100000).
The second line contains n numbers.
All the numbers are positive and less than of equal to 5000000.
Output
For each test case, if Alice can win, output “Alice”, otherwise output “Bob”.
Sample Input
2
2 2
3
2 2 4Sample Output
Bob
AliceSource
yehuijie
Manager
wuyiqi
n個の数を与え、2つの順番に任意の数nを選択して操作し、第1の操作はこの数を彼の因子に変えることであるが、それ自体に変えることはできない.
2つ目は、a*b=nを満たす2つの数aとbになります.ａ>1, b>1.
初めて線形ふるいを書くと、このアルゴリズムは普通のふるい法とは少し違いますが、もっと理解しにくいです.つまり、アルゴリズムは数ごとに
彼の最小の質因子はふるいにかけた.アルゴリズムの時間が線形であることも保証されている.
Accepted Code:
/************************************************************************* > File Name: 1112.cpp > Author: Stomach_ache > Mail: [email protected] > Created Time: 2014 09 05 11 35 09 > Propose: ************************************************************************/ #include <set> #include <cmath> #include <string> #include <cstdio> #include <fstream> #include <cstring> #include <iostream> #include <algorithm>
using namespace std; /*Let's fight!!!*/
const int MAX_N = 5000005; int n, pnum, p[MAX_N], mindiv[MAX_N], cnt[MAX_N]; bool vis[MAX_N]; // ， , //
void get_prime(int n) { pnum = 0; vis[1] = true; cnt[1] = 0; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[pnum++] = i; mindiv[i] = i; cnt[i] = 1; } for (int j = 0; j < pnum; j++) { if (p[j] * i > n) break; vis[p[j] * i] = true; mindiv[p[j] * i] = p[j]; cnt[p[j] * i] = cnt[i] + 1; if (i % p[j] == 0) break; } } } // ， -1
int sg[35]; int dfs(int n) { if (sg[n] != -1) return sg[n]; set<int> S; // a
for (int i = 0; i < n; i++) S.insert(dfs(i)); // a * b
for (int i = 1; i < n; i++) S.insert(dfs(i)^dfs(n - i)); int g = 0; while (S.find(g) != S.end()) g++; return sg[n] = g; } void get_SG() { get_prime(5000000); memset(sg, -1, sizeof(sg)); sg[0] = 0; for (int i = 1; i <= 33; i++) { sg[i] = dfs(i); } } int main(void) { get_SG(); // sg
int n; while (~scanf("%d", &n)) { int ans = 0; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); ans ^= sg[cnt[x]]; } if (ans) puts("Alice"); else puts("Bob"); } return 0; }