世纪难题——取石子游戏——题解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
int n,k;
int a[N],tree[N<<2],tag[N<<2];
int h[N],pw[N];
vector<string>q[N];
int ls(int p) {
	return p<<1;
}
int rs(int p) {
	return p<<1|1;
}
void push_up(int p) {
	tree[p]=tree[ls(p)]+tree[rs(p)];
	return;
}
void build(int p,int pl,int pr) {
	tag[p]=0;
	if(pl==pr) {
		tree[p]=a[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
	return;
}
void addtag(int p,int pl,int pr,int d) {
	tag[p]+=d;
	tree[p]+=d*(pr-pl+1);
	return;
}
void push_down(int p,int pl,int pr) {
	if(tag[p]) {
		int mid=(pl+pr)>>1;
		addtag(ls(p),pl,mid,tag[p]);
		addtag(rs(p),mid+1,pr,tag[p]);
		tag[p]=0;
	}
	return;
}
void updata(int L,int R,int p,int pl,int pr,int d) {
	if(L<=pl&&pr<=R) {
		addtag(p,pl,pr,d);
		return;
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(L<=mid)updata(L,R,ls(p),pl,mid,d);
	if(R>mid)updata(L,R,rs(p),mid+1,pr,d);
	push_up(p);
	return;
}
int query(int L,int R,int p,int pl,int pr) {
	if(L<=pl&&pr<=R)return tree[p];
	int mid=(pl+pr)>>1,res=0;
	push_down(p,pl,pr);
	if(L<=mid)res+=query(L,R,ls(p),pl,mid);
	if(R>mid)res+=query(L,R,rs(p),mid+1,pr);
	return res;
}
int gethash(int l,int r) {
	return((h[r]-h[l-1]*pw[r-l+1])%mod+mod)%mod;
}
int hassh(string book) {
	int res=0;
	for(int i=0; i<book.length(); i++)res=(book[i]+res*31%N);
	return res;
}
void insert(int key,string book) {
	int l=q[key].size();
	for(int i=0; i<l; i++)
		if(q[key][i]==book)
			return;
	q[key].push_back(book);
}
bool find(int key,string book) {
	int l=q[key].size();
	for(int i=0; i<l; i++)
		if(q[key][i]==book)
			return 1;
	return 0;
}
signed main() {
	scanf("%lld%lld",&n,&k);
	if(n%(k+1))cout<<1;
	else cout<<2;
	return 0;
}