【AtCoder Regular Contest 091 F】Strange Nim | Mrsrz's blog

博弈论，找规律。

题目大意：

有 $n$ 堆石子，第 $i$ 堆有 $A_i$ 个石子，并且有系数 $K_i$。

每次可以从一堆石子中取 $x$ 个，必须满足 $1\leq x\leq \lfloor\frac{A_i}{K_i}\rfloor$。不能取者输。

问是否先手必胜。

题解：

打表找 SG 函数的规律。

可以得到：

$$sg \left( n, K \right) = \begin{cases} \dfrac nK & K \mid n \\ n - \left \lfloor \dfrac nK \right \rfloor - 1 & K \nmid n \end{cases} \\$$

然后整除分块计算即可。

时间复杂度 $O(\sum\sqrt {A_i})$。

证明不会

Code：

#include<cstdio>
int n,g,A,K;
int main(){
    for(scanf("%d",&n);n--;g^=A/K)for(scanf("%d%d",&A,&K);A>K&&A%K;)A-=(1+(A%K-1)/(A/K+1))*(A/K+1);
    puts(g?"Takahashi":"Aoki");
}