51nod_1831: 小C的游戏（Bash博弈找规律）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

此类博弈不需要考虑sg函数，只需要确定必胜态和必败态，解题思路一般为打败先打表找规律，而后找规律给出统一的公式。打表方式：给定初始条件（此题中为ok[0]=ok[1]=0），然后从低到高枚举某一状态的所有次态，若有存在必败次态，则当前状态为必胜态，否则当前状态必败。

题意：对单独一堆石子，支持两种操作：1、石子数-1；2、石子数变为原来石子数的某一因数。取走走后一堆或无法操作（面对n==0，坑啊。。）者为负。

先打表找下规律

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long LL;

 ];

 void init()
 {
     ok[]=ok[]=;
     ; i<=; i++)
     {
         ])
         {
             ok[i]=;
             continue;
         }
         ; j<=i/; j++)    //分成等量j份，每份i/j个
              && !ok[i/j])
             {
                 ok[i]=;
                 break;
             }
     }
 }

 void print()
 {
     ; i<=; i++)
         printf("i=%d\tok[%d]=%d\n",i,i,ok[i]);
 }

 int main()
 {
     init();
     system("pause");
     print();
 }

打表

发现质数除了2和17都是败的，合数除了16,34和289都是赢的。我们发现2,4,8都是赢的（都可以通过-1到达必败态，而16的后继状态都是赢的，所以它是败的，而2^n(n>4)都能转化到16。同样的我们能说明17，34和2^n，17^m。

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long LL;

 bool is_prime(LL x)
 {
     ) return false;
     ;i*i<=x;i++)
         ) return false;
     return true;
 }

 int T;
 LL n;

 int main()
 {
     cin>>T;
     while(T--)
     {
         cin>>n;
         bool flag;
         if(is_prime(n))
         {
             ||n==) flag=true;
             else flag=false;
         }
         else
         {
             ||n==||n==||n==) flag=false;
             else flag=true;
         }
         puts(flag? "TAK":"NIE");
     }
 }

AC代码