Duel of Frequencies (Editorial)

Tutorial

Let $A$ be the number of stones divisible only by $X$, and $B$ be the number of stones divisible only by $Y$. Stones divisible by neither are useless.

Stones divisible by both $X$ and $Y$ grant an immediate extra move, meaning taking one does not pass the turn to the opponent. Because a player's turn sequence only truly ends when they pick an exclusive stone (an $A$ stone for Kael, or a $B$ stone for Liora), the shared stones merely delay the inevitable without altering the overall balance of turns.

The game reduces to a simple battle of attrition over the exclusive stones:

• Kael consumes exactly one $A$ stone per turn sequence, and Liora consumes exactly one $B$ stone.

• Since Kael goes first, he must have strictly more exclusive stones than Liora to outlast her.

• If A > B, Kael wins. Otherwise, if A \le B, Liora wins because she has enough stones to match Kael's moves until he runs out.

Complexity Time Complexity: $\mathcal{O}(N)$ per testcase to check divisibility and count stones, resulting in \mathcal{O}(\sum N) overall.

Space Complexity: $\mathcal{O}(1)$ auxiliary space.