Problem: A pile has $$$n$$$ stones and 2 players: Player A go first. Each move, the player will take $$$k$$$ stones from the pile, where $$$k$$$ is a prime number. Whoever can't make a move first is lost. Problem has multiple test. Constraints: $$$1 <= t <= 100$$$: Number of tests $$$2 <= n <= 3 \cdot 10^6$$$: The number of stones in the pile Output: A if A wins, B if B wins.
(Idk if it is a nim problem or not, that's the reason of the question mark) (Also, when I do $$$O((n)^2)$$$, I do precalculation: $$$res[0]=res[1]=0$$$(base case), $$$res[i]=1$$$ only if exist a prime $$$p$$$ where $$$res[i-p]=0$$$, else $$$res[i]=0$$$)
its not a nim problem though (get it?)
Idk if it is, that's the reason of the question mark :v
Try applying sprague grundy theorem, You'll notice a pattern in it and after noticing it, you can come up to an O(1) solution.
You can study it from here How to calculate Grundy values?.
Pattern looks somewhat like this g(x) = x % 4
Basically player B wins only when n % 4 == 0 otherwise A wins.
So not always B wins when n % 4 == 0
bs logic
Some more possible variations of Nim to brighten your day