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.
For example, 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.
Hint:
If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
当石子的个数不能被4整除时，总是可以取得胜利。
首先来考虑一些数量比较小的情况。很明显，在只有一个、两个或者三个石头的时候，并且轮到你了，把它们全拿走就可以获胜。如题目描述里所说，如果正好有四个石头，那么你就会输掉。因为不管你拿多少块，总会留下一些石头给对手，并且对手可以一次拿完。所以，为了确保胜利，你必须确保在轮到你时，不会出现只有四块石头的情况。
类似的，如果有五块、六块或者七块石头，你可以通过拿走足够的石头，从而给对手留下四块石头，那么对手就会输掉。但是，如果有八块石头，毫无疑问你会输。因为不关你是拿一块、两块还是三块，对手都可以确保轮到你时还剩四块，那样的话你就输了。
很明显，当石堆有4块、8块、12块、16块。。。时，你都会输，也就是说只要有4的倍数块石头，你就会输。
class Solution { public: bool canWinNim(int n) { return n%4 != 0; } };参考文献：Nim
