题目地址
题解
先大力打表,看SG函数有没有什么规律
发现打表结果非常神奇:
当$K$是奇数的时候,SG函数是$010101$变化的。
$K$是偶数的时候,每逢$K$的倍数,$SG(xcdot 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
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> #define INF 2000000000 using namespace std; typedef long long ll; int (){ 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("%dn",ans); else { for(int j=1;S-j>=0;j*=k) if(!SG(S-j)){ printf("%dn",j); break; } } } } int main(){ solve(); return 0; }
|
近期评论