F. Strange Nim | AtCoder Regular Contest 091

問題
二人でニムっぽいゲーム
山N個
各山A[i]個の石
山iから1<=a<=floor(X/K[i])個取れる
A[i]=0, 1<=i<=N の状態で自分のターンになったら負け
1<=N<=200
1 <= A[i], K[i] <= 10^9


解説
Grundy数がわかればいい。
g(x, k) : x個の山, k個取れるときのGrundy
k>xのとき
g(x, k) = 0
k=1, x>0 のとき
g(x, k) = 1
それ以外の場合
1<=y<=floor(x/k)
をすべて試すのは無理
実験すると規則が見つかる
k ∣ n のとき
g(n, k) = n/k
k ∤ n のとき
g(n, k) = g(n-floor(n/k)-1, k)
kが大きいとき時間かかりそう
floor(n, k) = aとおく
k ∣ n または floor(n, k) = a-1
となるまで一気にnからa+1を引こう。i回引くとして
n-(a+1)*i <= k*a
となればいい
よって
(n-ka)/(a+1) <= i
最小のi回a+1を引く