Hints: Divisibility Game

Fix a value $y$ that still appears in $b$. When is it possible for Alice to remove this $y$ on her turn? When is it possible for Bob to remove this $y$ on his turn? (Use only the rules: Alice needs some $x$ from $a$ with $x \mid y$; Bob needs some $x$ with $x \nmid y$.)

Answer to Hint 1: Alice can remove $y$ iff at least one entry of $a$ divides $y$. Bob can remove $y$ iff at least one entry of $a$ does not divide $y$.

So for a fixed $y$, if every entry of $a$ divides $y$, only Alice can ever take that copy of $y$. If no entry of $a$ divides $y$, only Bob can take it. If some divide and some do not, both players might be able to take that $y$ (Alice picks a divisor from $a$, Bob picks a non-divisor).

The arrays are huge, but values are bounded: $a_i, b_i \le n+m$. You only care about how many times each integer appears in $a$ and in $b$. What frequency arrays should you maintain so you can aggregate over all copies of each value in $b$ later?

Answer to Hint 3: Let $\mathrm{cnta}[v]$ be how many times $v$ appears in $a$, and $\mathrm{cntb}[v]$ how many times $v$ appears in $b$. The actual order in $a$ and $b$ does not matter for divisibility—only counts per value.

For a candidate $y$, you need to know how many entries of $a$ (with multiplicity) have value dividing $y$. If that number is $n$, every entry of $a$ divides $y$. If it is $0$, none do. If it is strictly between $0$ and $n$, the situation is “mixed.”

How can you compute, for all $y$ up to $n+m$, the sum of $\mathrm{cnta}[d]$ over every divisor $d$ of $y$—efficiently in $O((n+m)\log(n+m))$ or similar?

Answer to Hint 5: For each $d$, add $\mathrm{cnta}[d]$ to every multiple of $d$: for $y = d, 2d, 3d, \ldots \le n+m$. After processing all $d$, the accumulated value at index $y$ equals $\sum_{d \mid y} \mathrm{cnta}[d]$, i.e. the number of elements of $a$ whose value divides $y$.

Split all copies of numbers in $b$ into three groups using the count from Hint 6 (call it $\mathrm{cov}[y]$ for value $y$):

• Alice-only: $\mathrm{cov}[y] = n$ (every $a$-entry divides $y$).
• Bob-only: $\mathrm{cov}[y] = 0$ (no $a$-entry divides $y$).
• Either: $0 < \mathrm{cov}[y] < n$.

Let $C_A$ be the total number of $b$-elements (with multiplicity) in Alice-only values, $C_B$ for Bob-only, and $C_C$ for Either. How do these three totals relate to who wins?

Answer to Hint 7: Think strategically. Alice will eventually remove every Alice-only $b$-entry—Bob never can. Bob will eventually remove every Bob-only entry—Alice never can. The Either entries are the only ones where both players might have a legal move; play on those can “steal” turns and interact with who runs out of moves first.

Try to argue that optimal play reduces to comparing $C_A$ and $C_B$, with the parity of $C_C$ (even vs odd) flipping a tie case.

Imagine all Either positions were resolved first (both players only removing those $y$ while they still exist). Each such move removes one $b$-element. While $C_C > 0$, does the player to move always have a legal move on an Either value? (Remember: for such $y$, there is both a divisor and a non-divisor in $a$.)

Answer to Hint 9: Yes—as long as some Either-labeled value remains in $b$, the current player can always choose that $y$ and pick $x$ from $a$ according to their rule (Alice picks a dividing $x$, Bob a non-dividing $x$). So the two players alternate strictly on those $C_C$ moves until they are gone; Alice moves first globally, so who takes the last Either move depends on the parity of $C_C$.

After all $C_C$ Either moves, only Alice-only and Bob-only values can remain. From then on, can the players ever remove the other side’s exclusive values? What simple “race” remains?

Answer to Hint 11: After Either’s are gone, Alice can only shrink the Alice-only pile; Bob can only shrink the Bob-only pile. They keep alternating until one player cannot move. If $C_A > C_B$, Alice clears Bob-only first (Bob runs out of Bob-only before Alice runs out of Alice-only in the head-to-head), and Alice still has moves—she wins. If $C_A < C_B$, Bob wins. If $C_A = C_B$, whoever must move next after the Either phase loses (no Either left, both exclusive piles same size—symmetric deadlock for the player to move).

Combine parity of $C_C$ with the tie case $C_A = C_B$. Alice plays first overall. After exactly $C_C$ moves on Either values (alternating strictly), who is to move next—Alice or Bob—when $C_C$ is even vs odd? (Count: move $1$ is Alice, move $2$ is Bob, …)

Answer to Hint 13: After even $C_C$, it is Alice’s turn again. With $C_A = C_B$ and only exclusive values left, simulate: Alice always shrinks $C_A$, Bob always shrinks $C_B$; with equal starting piles and Alice moving first, Alice empties her pile first and then cannot move on Bob’s remaining exclusive values—Bob wins the tie.

After odd $C_C$, it is Bob’s turn first on the exclusive race; the same symmetric argument swaps roles—Alice wins the tie when $C_A = C_B$.

When $C_A \ne C_B$, the strict inequality $C_A > C_B$ vs $C_A < C_B$ decides the winner regardless of parity (parity only matters when the exclusive counts would otherwise tie).

Implementation checklist: compute $\mathrm{cov}[y]$ for all $y \le n+m$ by divisor-sweep; accumulate $C_A$, $C_B$, $C_C$ using $\mathrm{cntb}[y]$; then:

• if $C_C$ is even: Alice iff $C_A > C_B$;
• if $C_C$ is odd: Alice iff $C_A \ge C_B$.

This is exactly the “exclusive race” plus parity of the Either phase: even $C_C$ leaves Alice first on exclusives (strict $>$ for her when $C_A = C_B$ she loses); odd $C_C$ leaves Bob first ($\ge$ flips the tie toward Alice).