题目描述
Mojtaba and Arpa are playing a game. They have a list of $n$ numbers in the game.
In a player’s turn, he chooses a number $p^k$ (where $p$ is a prime number and $k$ is a positive integer) such that $p^k$ divides at least one number in the list. For each number in the list divisible by $p^k$, call it $x$, the player will delete $x$ and add ${x \over p^k}$ to the list. The player who can not make a valid choice of $p$ and $k$ loses.
Mojtaba starts the game and the players alternatively make moves. Determine which one of players will be the winner if both players play optimally.
算法分析
给定一个长度为$n$的序列,两人轮流进行操作,每次操作给定$p, k$,其中$p$是素数,$k$是正整数,将序列中所有能被$p^k$整除的数除以$p^k$(要求至少有一个数能被整除),不能进行操作的人算输。问在两人都采取最优策略的情况下,先手必胜还是后手必胜。
数据范围:$1 \le n \le 100, \; 1 \le a_i \le 10^9$。
算法分析
考虑某个质数$p$,它对其他质数不产生任何影响,因此可以分别处理每个质数。
设处理到的质数是$p$,我们计算出它在序列每个数中的最高次数,并储存在二进制数s
中。那么在进行一次$p, k$操作后,s
会被更新成(s>>k)|(s&((1<<(k-1))-1))
。把s
看成点,操作看成边,就构成了一张有向图。分别计算每个质数有向图的SG函数,异或起来,如果等于$0$则后手必胜,否则先手必胜。
代码
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <map> using namespace std; namespace std { template <typename T> void maxify(T &a, T b) { b > a && (a = b); } template <typename T> void minify(T &a, T b) { b < a && (a = b); } } struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline IOManager operator > (T &x) { read(x); return *this; } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char c) { putchar(c); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } template <typename T> inline IOManager operator < (T x) { write(x); return *this; } } io; struct Solver { private: static const int N = 100; int n, a[N + 1]; map <int, int> sg, num; void input() { io > n; for (int i = 1; i <= n; ++ i) io > a[i]; } void init() { for (int i = 1; i <= n; ++ i) if (a[i] > 1) { int q = sqrt(a[i]); for (int j = 2; j <= q; ++ j) { if (a[i] == 1) break; if (! (a[i] % j)) { int cnt = 0; while (! (a[i] % j)) a[i] /= j, ++ cnt; num[j] |= 1 << cnt - 1; } } if (a[i] > 1) num[a[i]] |= 1; } } int get_sg(int t) { if (! t) return 0; if (sg.count(t)) return sg[t]; map <int, bool> vis; int p = t, cnt = 0; while (p) p >>= 1, ++ cnt; for (int i = 1; i <= cnt; ++ i) vis[get_sg((t >> i) | (t & (1 << i - 1) - 1))] = true; cnt = 0; while (vis[cnt]) ++ cnt; return sg[t] = cnt; } void process() { int ans = 0; for (map <int, int> :: iterator it = num.begin(); it != num.end(); ++ it) ans ^= get_sg(it->second); if (! ans) io < (char *) "Arpa\n"; else io < (char *) "Mojtaba\n"; } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }