Divisibility Game

Research note: I checked the official Codeforces editorial page, the CF Step model solution, and the CF Step hints. The official tutorial text was not loaded there, but the available model code matches the three-bucket approach below. The proof here is reconstructed from the statement.

The key move is to stop thinking about individual choices of $x$. For a fixed remaining copy of value $y$ in $b$, define

$cover[y]=\sum_{d | y} cntA[d].$

This is the number of entries of $a$ that divide $y$, with multiplicity.

Now classify every copy of every value in $b$:

• If $cover[y]=n$, then every $x$ in $a$ divides $y$. Alice can remove it, Bob cannot. Call it Alice-only.
• If $cover[y]=0$, then no $x$ in $a$ divides $y$. Bob can remove it, Alice cannot. Call it Bob-only.
• If $0<cover[y]<n$, then Alice can pick a dividing $x$, and Bob can pick a non-dividing $x$. Call it shared.

Let the total numbers of these copies be $A$, $B$, and $C$.

At this point the original divisibility game becomes a tiny abstract game:

• Alice may remove one token from $A$ or $C$.
• Bob may remove one token from $B$ or $C$.
• Whoever has no legal token on their turn loses.

No Sprague-Grundy circus needed. The important false assumption to kill is: private tokens are not always good to spend early. If shared tokens exist, spending your private tokens can just make you run out sooner. Shared tokens are the contested tempo.

First solve the exclusive-only case, $C=0$.

If Alice moves first and only $A,B$ remain, Alice wins iff $A>B$. They alternate removing their own exclusive tokens. If $A<=B$, Alice runs out first or exactly together, and then it is Alice's turn with no move. If $A>B$, Bob runs out first.

If Bob moves first in the same exclusive-only game, Alice wins iff $A>=B$, because now Bob is the one who must survive the equal-count race while moving first.

Shared tokens only decide whose turn starts that exclusive race. Since both players can always remove a shared token while $C>0$, the first $C$ shared removals can be viewed as alternating neutral moves. Alice starts:

• If $C$ is even, after all shared tokens are gone, it is Alice's turn. Alice then needs $A>B$.
• If $C$ is odd, after all shared tokens are gone, it is Bob's turn. Alice then needs $A>=B$.

This gives the final rule:

$$\text{Alice wins} \iff \begin{cases} A>B, & C \text{ even},\\ A>=B, & C \text{ odd}. \end{cases}$$

For completeness, here is the induction version of the proof, since this is where bugs like to hide. Let $W_A(A,B,C)$ mean Alice wins when it is Alice's turn, and $W_B(A,B,C)$ mean Alice wins when it is Bob's turn. The claims are:

$W_A(A,B,C) \iff A+(C \bmod 2)>B,$

and

$W_B(A,B,C) \iff A>=B+(C \bmod 2).$

For $C=0$, these are exactly the exclusive race above. For $C>0$, a shared move flips the turn and changes only the parity of $C$, so the condition transforms into the matching condition for the other player. A private move can only decrease your own future supply, so when the formula says you are losing, it cannot magically save you; checking the inequalities after decreasing $A$ or $B$ confirms that. That proves the rule.

Now compute the buckets efficiently.

Values satisfy $a_i,b_i <= n+m$. Let $L=n+m$. Build frequency arrays $cntA$ and $cntB$ of size $L+1$. To compute $cover[y]$ for every $y$, sweep divisors:

$cover[kd] += cntA[d] \quad \text{for } k=1,2,3,\dots$

The total work is

$\sum_{d=1}^{L} \frac{L}{d}=O(L\log L).$

Then scan all $y$ with $cntB[y]>0$ and add $cntB[y]$ to the correct bucket by comparing $cover[y]$ with $0$ and $n$.

Edge cases:

• If $a$ contains only $1$, then every $b$ value is Alice-only. Bob is cooked.
• If no $a_i$ divides some $y$, that copy is Bob-only even if $y$ appears many times.
• Duplicates matter only as multiplicities, and $cover[y]$ counts them correctly.
• If $C=0$, the answer is just the strict comparison $A>B$ because Alice moves first.

Complexity per test case is $O((n+m)\log(n+m))$ time and $O(n+m)$ memory. Across all tests, the input sums keep this easily within limits.