strangenim

pengyule · 2022-04-08 19:43:52 · 题解

忘得好快，把题解保存到洛谷。

p2.含参 k[i]

每次可以取一堆的 [1,\lfloor a_i/k_i\rfloor] 个的 nim。n\le 200,a_i,k_i\le 10^9

解法：打表找规律：当 A%k==0 时 SG(A)=\frac Ak，否则SG(A)=SG(A-A/k)(/表示整除)。就可以根号分治。k>\sqrt n，暴力减，直到——；k\le \sqrt n，根据整除分块的思想，可以 O(1) 跳完一个块，而块数 \le\sqrt n。

#include <bits/stdc++.h>
using namespace std;
int n,x,k,ans;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>k;
        bool flag=0;
        for(;1ll*k*k<=x;x-=1+x/k)if(x%k==0){ans^=x/k;flag=1;break;}
        if(!flag){
            while(x>=k){
                int s=x/k;
                x-=(x-s*k)/(1+s)*(1+s);
                if(x%k==0){ans^=s;break;}
                x-=1+s;
            }
        }
    }puts(ans?"Takahashi":"Aoki");
}