You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
Example:
Input: 4
Output: false
Explanation: If there are 4 stones in the heap, then you will never win the game;
No matter 1, 2, or 3 stones you remove, the last stone will always be
removed by your friend.
思路参考这里
这里做一个抽象，假设一推里面有n个石头，每次可以取 1-m 个石头。
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。这里我们就有一个想法了，假设这个石头推为 (m+1)的倍数，那么第一个人取k( 1 <= k <= m)个，只要第二个人取 (m+1-k)个石头，那么必定状态能回到最初的状态，m+1个。因为每个人都是很聪明的，取的石头的个数一定要对自己有利。那么，假设最初石头推不为 (m+1)的倍数。n=（m+1）r+s，那么第一个人只要取s个石头必定能获得胜利，反之，如果s == 0 ，那么第一个人必输。
即，若n=k*(m+1)，则后取着胜，反之，存在先取者获胜的取法。n%(m+1)==0. 先取者必败。
class Solution { public: bool canWinNim(int n) { return (n)%4==0?0:1; } };
