Arpa and a Game with Mojtaba

题目描述

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;
}