[ARC155D] Avoid Coprime Game

一个暴力思路是直接记录选了哪些 \(a\) 然后转移，但是我们显然没办法将已选择的 \(a\) 的信息用状压全部记录下来。但是你注意到题目中对 \(a\) 的选择有着不错的性质，具体如下：

• 若确定当前 \(G\)，则先前选择的所有 \(a_i\) 均满足 \(G | a_i\)。
• 若经过若干次操作后已有 \(G | a_i\)，则此后我们不再关心 \(a_i\) 的具体值。

这似乎告诉我们，在确定了 \(G\) 的情况下，我们只需记录已选择的 \(G | a_i\) 的个数。进一步，只需记录这样的 \(a_i\) 的个数的奇偶性即可，因为只和当前轮到谁操作有关。同时，在转移时我们可以随心所欲地选择哪些可以令 \(G\) 减小的 \(a_i\) 因为他们在先前从未被选择。

这就导出了一个状态数 \(O(n)\) 的 DP。设 \(f_{i,0/1}\) 表示当前 \(G=i\)，此时轮到哪个人操作。转移有两类：

• 若存在 \(j | i\) 使得存在 \(\gcd(i,a_k) = j\)，则 \(f_j\) 可转移至 \(f_i\)。
• 若 \(i\) 的所有后继状态皆为必败态，则两人一直取 \(i\) 的倍数，最终胜者可根据 \(i\) 倍数个数的奇偶性决定。

最后，我们只需解决这样一个问题：对 \((i,j)\) 判断是否存在 \(a_k\) 使得 \(\gcd(i, a_k) = j\)。考虑若 \(j = i\) 则就是一个狄利克雷后缀和。对于 \(j < i\) 的情况会多算 \(j\) 的倍数，那么在计算的过程中容斥掉即可。最终复杂度是两个调和级数的 \(O(N \log^2 N)\)。

const int N = 2e5;
int n, a[N + 10], cnt[N + 10];
int f[N + 10][2], buc[N + 10];
vector<int> v[N + 10];

int main() {
  read(n);
  for(int i = 1; i <= n; ++i)
    read(a[i]), ++cnt[a[i]];
  for(int i = 2; i <= N; ++i)
    for(int j = i; j <= N; j += i) {
      v[j].emplace_back(i);
      if(j > i) cnt[i] += cnt[j];
    }
  for(int i = 2; i <= N; ++i) {
    for(int x : v[i])
      buc[x] = cnt[x];
    int flag = false;
    for_each(v[i].rbegin(), v[i].rend(), [&](int x) {
      if(x != i && buc[x]) {
        if(!f[x][0]) flag = f[i][1] = true;
        if(!f[x][1]) flag = f[i][0] = true;
      }
      for(int y : v[x])
        buc[y] -= buc[x];
    });
    if(!flag) f[i][cnt[i] % 2] = true;
  }
  for(int i = 1; i <= n; ++i)
    puts(f[a[i]][0] ? "Aoki" : "Takahashi");