<p>Alice and Bob take turns playing a game, with Alice starting first.</p>

<p>Initially, there are <code>n</code> stones in a pile. On each player&#39;s turn, that player makes a <em>move</em> consisting of removing <strong>any</strong> non-zero <strong>square number</strong> of stones in the pile.</p>

<p>Also, if a player cannot make a move, he/she loses the game.</p>

<p>Given a positive integer <code>n</code>, return <code>true</code> if and only if Alice wins the game otherwise return <code>false</code>, assuming both players play optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> true
<strong>Explanation: </strong>Alice can remove 1 stone winning the game because Bob doesn&#39;t have any moves.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> false
<strong>Explanation: </strong>Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -&gt; 1 -&gt; 0).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> true
<strong>Explanation:</strong> n is already a perfect square, Alice can win with one move, removing 4 stones (4 -&gt; 0).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

using namespace std;
typedef uint64_t ll;
class Solution {
	const vector<int64_t> ref ={
		-2706003,
		-1074790533,-2367755,-4327441,-295977,-554190915,
		-4257,-32769,-661,-8654849,-20973569,
		-524293,-17039363,-675414017,2078277631,-537133057,
		-1,-8454209,-671088641,-1,2080374783,
		-1048609,-276824065,-17,-1241513985,-16777217,
		-167777281,-268435489,-537395717,-1073750273,-1,
		-1073741841,-8454145,-16797697,-33,-2170945,
		-5243009,-278923265,-513,-4225,-335552769,
		-134217729,-1,-1,-1,-16793601,
		-1073741825,-1,-536870913,-33,-536871169,
		-5,-33554433,-129,-268435457,-1,
		-1,-65,-129,-8193,-268435457,
		-33797,-67379201,-134217729,-1,-2097153,
		-1,-1,-1,-1074831369,2147483647,
		-4325409,-67108865,-540805,-8658945,-2163201,
		-145,-67373121,-134234113,-1025,-16387,
		-1085441,2145320695,-513,-9438241,-524289,
		-5247105,-1281,-65537,-294913,-17301505,
		-131205,-32769,-513,-276824065,-536872961,
		-1,-268435457,-536870913,-1074790401,2147475455,
		-1,-1342178305,-1,-1073745921,-17,
		-1,-3,-1,-1,2147483647,
		-131073,-2162689,-524289,-1,-65545,
		-134217729,-1,-16777221,-2130945,-1,
		-155189249,-1,-4097,-1057,-65,
		-129,-8193,-17,-33793,-540675,
		-131077,-2097161,-533,-262409,-536870915,
		-1,-265,-4225,-8388609,-536871425,
		-1,-67117057,-536870913,-1108344833,-67108865,
		-1041,1879048191,-1,-1048577,2147483647,
		-4325377,-268435457,-16777217,-33554433,-620757057,
		-1,-67141665,-134221825,-1,-1,
		-1,-33554433,-524289,-1,-65603,
		-4097,2139095039,-16777745,-1,-67585,
		-1052673,-1,-536936449,-268436481,-536870913,
		-1,-134217729,-149,-8650753,-1,
		-1,-3,-131077,-1,-17,
		-33,-1,-134217729,-1,-16385,
		-1,-262147,-1,-1048577,-1,
		-134348801,-8388609,-16897,-33816577,-16844801,
		-135430145,-33562625,-557842433,-32769,-2049,
		-1,-2049,-524801,-1,-2049,
		-1048577,-1,-2065,-262177,-513,
		-1052677,-2097153,-513,-8396801,-524289,
	};
public:
    bool winnerSquareGame(int n) {
		return gen(n);
		int i = n/64;
		int j = n%64;
		int64_t mask =1;
		if(j != 0)
			mask = mask << (j-1);
		return ref[i] & mask;
    }

	bool gen(int test){
		ll n = 100032;
		vector<bool> ans(n+1, false);
		for(ll i = 1; i<n; i++){
			ll s = i*i;
			if(s>n)
				break;
			ans[s]=true;
		}

		for(ll i=1; i<=n; i++){
			if(ans[i]){
				continue;
			}
			for(ll j = 1; j<i; j++){
				if(j*j>i) break;
				if(!ans[i-(j*j)]){
					ans[i] = true;
					break;
				}
			}
		}
		return ans[test];
		vector<int> nums(n/64);
		for(int i = 0; i<n/64; i++){
			ll num = 0;
			for(int j=0; j<64; j++){
				int pos = 64*i + j;
				if(ans[pos]){
					ll mask = 1;
					if(j!=0)
						mask = mask << (j-1);
					num = num | mask;
				}
			}
			nums[i] = num;
		}
		
		for(int i = 0; i<nums.size(); i++){
			cout<<nums[i]<<',';
			if(i % 5 == 0)
				cout<<endl;
		}
	}

};

8795