题目链接:A - The game of Osho
思路:SG打表找规律,发现在b为奇数时,0、1均匀分布,b为偶数时且满足n%(b+1) = b时sg值为2,打表程序如下:
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 1e5+10;
ll b,_;int n;
int f[N];
int sg(int id){
if(f[id] != -1)return f[id];
set<int>S;
ll p = 1;
while(p<=id){
S.insert(sg(id-p));
p=b*p;
}
int now = 0;
while(S.count(now))now++;
f[id] = now;
return now;
}
void solve(){
while(true){
memset(f,-1,sizeof f);f[0] = 0;f[1] = 1;
read(b);read(n);
rep(i,0,n){
if(sg(i)==2)printf("%d\n",i);
}
}
}
signed main(){solve(); return 0; }
AC代码如下:
#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int N = 1e5+10;
ll b,_;int n;
int f[N];
int sg(int id){
if(f[id] != -1)return f[id];
set<int>S;
ll p = 1;
while(p<=id){
S.insert(sg(id-p));
p=b*p;
}
int now = 0;
while(S.count(now))now++;
f[id] = now;
return now;
}
void solve(){
freopen("powers.in","r",stdin);
read(_);
while(_--){
int t;
read(t);
int ans = 0;
rep(i,1,t){
read(b);read(n);
if(b & 1){
ans ^= n%2;
}
else if(n%(b+1) == b)ans^=2;
else {
int x = n%(b+1);
ans ^= x%2;
}
}
if(!ans)puts("2");else puts("1");
}
}
signed main(){solve(); return 0; }