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

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

先打表找下规律

1 #include
      
        2 using namespace std; 3 typedef long long LL; 4  5 int ok[1010]; 6  7 void init() 8 { 9     ok[0]=ok[1]=0;10     for(int i=2; i<=1000; i++)11     {12         if(!ok[i-1])13         {14             ok[i]=1;15             continue;16         }17         for(int j=2; j<=i/2; j++)    //分成等量j份，每份i/j个18             if(i%j==0 && !ok[i/j])19             {20                 ok[i]=1;21                 break;22             }23     }24 }25 26 void print()27 {28     for(int i=0; i<=1000; i++)29         printf("i=%d\tok[%d]=%d\n",i,i,ok[i]);30 }31 32 int main()33 {34     init();35     system("pause");36     print();37 }
      

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

1 #include
      
        2 using namespace std; 3 typedef long long LL; 4  5 bool is_prime(LL x) 6 { 7     if(x<2) return false; 8     for(LL i=2;i*i<=x;i++) 9         if(x%i==0) return false;10     return true;11 }12 13 int T;14 LL n;15 16 int main()17 {18     cin>>T;19     while(T--)20     {21         cin>>n;22         bool flag;23         if(is_prime(n))24         {25             if(n==2||n==17) flag=true;26             else flag=false;27         }28         else29         {30             if(n<2||n==16||n==34||n==289) flag=false;31             else flag=true;32         }33         puts(flag? "TAK":"NIE");34     }35 }