[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");