Your game with piles of $S_1,\ldots,S_N$ stones is identical to the Nim game with piles of $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$ stones. So you can pretend that you are playing Nim, and follow the usual Nim strategy.
For example, suppose we have piles $S_1 = 3, S_2 = 4, S_3 = 7$. We can pretend this is a Nim game with piles 3, 2, and 2, and play accordingly. In this case there are several winning Nim moves. One such is to take 1 stone from the third pile; this corresponds to taking 3 stones from $S_3$, moving to $(3, 4, 4)$.
Addendum Sorry, I misread the question and thought a legal move was to remove any multiple of $i$ stones from pile $S_i$. But the game as given is even simpler. Again we pretend that instead of $S_1,\ldots,S_N$ the piles contain $S_1, \Bigl\lfloor \frac{S_2}2\Bigr\rfloor,\Bigl\lfloor \frac{S_3}3\Bigr\rfloor, \ldots , \Bigl\lfloor \frac{S_N}N\Bigr\rfloor$, and the rule is that a legal move removes one stone from any pile. It is now evident that a position is a win for the previous player if and only if
$$\sum{\biggl\lfloor \frac{S_i}{i} \biggr\rfloor}$$
is even, and that it doesn't even matter what moves are made.
There is really only one "move" in the game. Alice needs to decide who should go first. After that, both players are playing mechanically.
To decide who goes first, Alice finds the least X such that no subset of the available numbers adds up to X. Play will end on turn X, and Alice wants to be the one whose turn that is. So, if X is odd, Alice plays first; otherwise she lets Bob play first.
To easily determine X, Alice uses a Sieve. You're probably familiar with the Sieve of Eratosthenes, used to find primes. Same idea, but with different rules for a different purpose.
Alice writes down the numbers from 0 to the sum of all the numbers on the table, and crosses off 0. Then she takes numbers from the table, one at a time, without replacement. When she takes off the number Y, she crosses off every number that is Y plus some previously-crossed off number. When she has done this for every number on the table, the smallest un-crossed-off number is X.
Notice that this works even if the numbers on the table are not all distinct.
It even works if some of them are negative or zero, except that then Alice's initial list runs from the sum of the negative numbers thru the sum of the positive numbers, and X is the least positive un-crossed-off number.
Improved solution
Assume the numbers on the table are distinct positive integers.
If there were no missing numbers, any sum up to $S(N) = N(N+1)/2$ could easily be gotten, and X would be $S(N) = 1$.
But there are missing numbers. Let's start with an empty table, add numbers to it in increasing order, and after placing each number $n$ compute $S(n)$ = sum of all numbers on the table up to $n$. The question is, is it still true that a player could get any sum up to $S(n)$ from these numbers, assuming it was true for $S(n-1)$ before placing $n$.
Well, if $n \le S(n-1)+1$, then the answer is clearly yes. You could already get any sum up to $S(n-1)$ without using $n$. To get a sum $s$ where $S(n-1) \lt s \le S(n)$, combine $n$ with a combination summing to $s - n$ from the smaller numbers.
Conversely, if $n \gt S(n-1)+1$, then the answer is no. The sum $S(n-1)+1$ is unachievable without using $n$, because it exceeds the sum of the other numbers, and is also unachievable using $n$, because $n$ by itself is already too large.
And that leads to an obvious $O(N)$ algorithm to find X
X = 1
for n from 1 to N
break if n > X
X += n unless n is one of the missing numbers
end
return X
(I assume it's obvious how to do unless n is one of the missing numbers in constant time, assuming they are given to us in ascending order.)
But if $K$ is much smaller than $N$ we can do better. Suppose we're given the missing numbers in ascending order. Then
MSUM = 0
for each missing number m
MSUM += m
X = m * (m + 1)/2 - MSUM + 1
return X if m >= X
end
return N * (N + 1)/2 - MSUM + 1
This runs in time $O(K)$.
Best Answer
Alice wins when $N$ is not a power of 2.
Let $i(N)$ be the maximal $i$ such that $N$ is divisble by $2^i$.
Alice's strategy: If there are $m$ stones left, Alice picks $2^{i(m)}$ stones.
Let me explain why this strategy is winning for Alice. Assume that Bob won by picking $b > 0$ remaining stones. Assume that before that Alice picked $2^j$ stones. By definition $j = i(2^j + b)$. Hence $2^j + b$ is divisible by $2^j$. Therefore $b$ is also divisible by $2^j$. This means that $b\ge 2^j$. On the other hand by the rules of the game $b\le 2^j$. Therefore $b = 2^j$.
But then $i(2^j + b) = i(2^j + 2^j) = j + 1$, contradiction.
This strategy is correct because (a) since $N$ is not a power of 2, Alice picks less than $N$ stones in the first turn; (b) Alice never picks more stones than Bob in the previous turn. Indeed, assume that Bob picked $b$ stones, before Alice picked $2^j$ stones, and we are left with $m > 0$ stones.
Let us verify that $2^{i(m)} \le b$. We will do it by showing that $b$ is divisble by $2^{i(m)}$.
Indeed, by definition of Alice's strategy $j = i(2^j + b + m)$ and by the rules of the game $b\le 2^j$. Let us show that $i(m) \le j$. Indeed, if $i(m) > j$, then $b$ is divisble by $2^j$, since both $2^j + b + m$ and $m$ are divisble by $2^j$. But since $b\le 2^j$, this means that $b = 2^j$. This contradicts the fact that $j = i(2^j + b + m)$. Indeed, since $i(m) > j$, we have that $i(2^j + b + m) = i(2^{j + 1} + m) \ge j + 1$.
Thus we have proved that $i(m) \le j$. This means $2^j + b + m$ is divisble by $2^{i(m)}$, as well as $m$. Hence $b$ is also divisble by $2^{i(m)}$ as required.
Bob wins when $N$ is a power of 2. Assume that $N = 2^i$ and Alice picks $a$ stones. Then Bob can use Alice's strategy described above. We only have to check that Bob then picks at most $a$ stones. Indeed, assume that $j$ is such that $2^i - a$ is divisible by $2^j$. Then $a$ is also divisible by $2^j$ hence $2^j \le a$.