题解
先大力打表，看SG函数有没有什么规律
发现打表结果非常神奇：
当$K$是奇数的时候，SG函数是$010101$变化的。
$K$是偶数的时候，每逢$K$的倍数，$SG（x\cdot K）$就为$2$。
否则仍然按照$010101$变化。
比如$K=2:0,1,2,0,1,2 …$
$K=4:0,1,0,1,2,0,1,0,1,2…$
之后就简单了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int S,k,T;
int SG(int x){
if(k%2)return x%2;
else {
int mod=x%(k+1);
if(mod<k)return mod%2;
else return 2;
}
}
void solve(){
T=read();
while(T--){
S=read(),k=read();
int ans=SG(S);
if(ans!=2)printf("%d\n",ans);
else {
for(int j=1;S-j>=0;j*=k)
if(!SG(S-j)){
printf("%d\n",j);
break;
}
}
}
}
int main(){
solve();
return 0;
}