PE 301 Nim （Nim博弈）

骑猪看日落 2022-07-13 05:55 180阅读 0赞

## Nim ##

### Problem 301 ###

*Nim* is a game played with heaps of stones, where two players take it in turn to remove any number of stones from any heap until no stones remain.

We'll consider the three-heap normal-play version of Nim, which works as follows:  
\- At the start of the game there are three heaps of stones.  
\- On his turn the player removes any positive number of stones from any single heap.  
\- The first player unable to move (because no stones remain) loses.

If (n1,n2,n3) indicates a Nim position consisting of heaps of size n1, n2 and n3 then there is a simple function X(n1,n2,n3) — that you may look up or attempt to deduce for yourself — that returns:

*  zero if, with perfect strategy, the player about to move will eventually lose; or
 *  non-zero if, with perfect strategy, the player about to move will eventually win.

For example X(1,2,3) = 0 because, no matter what the current player does, his opponent can respond with a move that leaves two heaps of equal size, at which point every move by the current player can be mirrored by his opponent until no stones remain; so the current player loses. To illustrate:  
\- current player moves to (1,2,1)  
\- opponent moves to (1,0,1)  
\- current player moves to (0,0,1)  
\- opponent moves to (0,0,0), and so wins.

For how many positive integers n ≤ 230 does X(n,2n,3n) = 0 ?

题意：取石子游戏。

*  游戏开始时有三堆石子。
 *  每名玩家在轮到自己时从任意一堆中取走任意正数枚石子。
 *  轮到时已无石子可取的玩家输掉游戏。
 *  ，X(1,2,3) = 0，因为无论当前玩家如何操作，他的对手都能够给他留下两堆同样规模的石子并不断仿照他的操作直到石子全部取完；因此当前玩家必定会输掉游戏。  
    
    
    有多少个正整数n ≤ 230使得X(n,2n,3n) = 0？  
    
    
    题解：典型的Nim博弈...
    
    代码：
    
        #include<bits/stdc++.h>
        using namespace std;
        typedef long long ll;
        
        int main()
        {
            ll a,b,c;
            ll count=0;
        	for(int i=1;i<=(1<<30);i++)
        	{
        		a=i;
        		b=2*i;
        		c=3*i;
        		ll res=a ^ b^ c;
        		if(res==0)count++;
        	 } 
        	 cout<<count<<endl;
            return 0;
        }