Problem
有一堆石子共有N个。A B两个人轮流拿,A先拿。每次拿的数量只能是2的正整数次幂,比如(1,2,4,8,16....),拿到最后1颗石子的人获胜。假设A B都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。
例如N = 3。A只能拿1颗或2颗,所以B可以拿到最后1颗石子。(输入的N可能为大数)
Solution
打表发现3的倍数时为必败点,B赢。如果不是3的倍数可以-1或-2转移到3的倍数,必胜,考虑有没有可能后面出现一个3的倍数可以通过减2的幂转移到前面必败点,即3的更小倍数,化为表达式(3x-2^t)%3==0,很明显不能,那3的倍数就是必败点,其他是必胜点。
Code
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
| #include<iostream> #include<cstring> #include<algorithm> #define ll long long #define inf 0x7fffffffffffffff #define mem(a, x) memset(a,x,sizeof(a)) #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) typedef std::pair<int, int> Pii; typedef std::pair<ll, ll> Pll; ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; } ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); } ll _abs(ll x){return x < 0 ? -x : x;} using namespace std; int T; string s; int main(){ io_opt; cin>>T; while(T--){ cin>>s; ll cur=0; for(int i=0;i<s.size();i++){ cur*=10; cur+=s[i]-'0'; cur%=3; } if(cur==0){ cout<<"B"<<endl; } else{ cout<<"A"<<endl; } } return 0; }
|