Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: coderdhanraj
Tester: tabr
Editorialist: iceknight1093






There’s a pile with N stones. You also have an integer K.

Alice and Bob play a game, Alice starts first.
On their turn, a player can choose an integer x such that \gcd(x, K) = 1 and there are at least x stones remaining; and remove x stones from the pile.
The winner is the person who makes the last move.

Choose whether you play as Alice or Bob; and win the game.


First, we need to decide who we’re playing as.
For this, we need to know who wins the game, given N and K.

If K = 1 then every move is valid; so Alice wins on the first move by just removing all N stones.
We only need to deal with the K\gt 1 case.

\gcd is a function that depends on prime factorization; so intuitively this should have something to do with the prime factorization of K.

Indeed, if you work out a few small cases on paper, and especially observe which moves are possible for a given K, you might notice the following:

\text{Let } p \text{ be the smallest prime factor of } K. \\ \text{Alice wins if and only if } N\bmod{p} \neq 0.

That is, Alice wins if and only if p doesn’t divide N.
The proof of this also gives us a winning strategy.

The important observation that makes this work is that, if p is the smallest prime that divides K, then \gcd(K, x) = 1 for all 1 \leq x \lt p.
That is, the moves 1, 2, 3, \ldots, p-1 are always valid moves.
This is because \gcd(K, x) \gt 1 means K and x share a prime factor; but if x \lt p then K would have a prime factor smaller than p, which is a contradiction.

Further, if N\bmod{p} = 0, there’s no valid move x such that (N-x)\bmod{p} = 0.
Any such move would require x to be a multiple of p; but then \gcd(x, K) \gt 1 so it’s not a valid move.

Together, the above points tell us that:

  • If N\bmod{p} = 0, then the current player can only move to a non-zero state.
  • If N\bmod{p} \gt 0, the current player can always move to a zero state; because N\bmod{p} \lt p, it is enough (and always a valid move) to simply remove N\bmod{p} stones.

In particular, if N\bmod{p} \gt 0, the current player will always have a valid move; so they can never be lost.

Putting it all together, we have a fairly simple strategy:

  • If N\bmod{p} = 0, play as Bob.
    Otherwise, play as Alice.
  • This guarantees that on your turn, N\bmod{p} \gt 0.
    Simply remove N\bmod{p} stones, which is always possible.

Finding the smallest prime factor of K can be done in \mathcal{O}(\sqrt{K}) time.


\mathcal{O}(N + \sqrt{K}) per testcase.


Author's code (C++)
using namespace std;
void solve(){
    int n, k; cin >> n >> k;
    int x = k, sqK = sqrt(k);
    if (k == 1){
        cout << "Alice" << endl;
        cout << n << endl;
        cin >> x;
    for (int i = 2; i <= sqK; i++) if (k % i == 0){
        x = i;
    if (n % x){
        cout << "Alice" << endl;
        cout << n % x << endl;
    }else cout << "Bob" << endl;
    int ans;
    while (true){
        cin >> ans;
        if (ans == -1) exit(0);
        if (ans == 0) return;
        cout << (ans % x ? ans % x : 1) << endl;
int main(){
    int test; cin >> test;
    while (test--) solve();
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#define debug(...)

int main() {
    int tt;
    cin >> tt;
    int sn = 0;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        sn += n;
        cerr << n << " " << k << endl;
        assert(1 <= n && n <= 1e6);
        assert(1 <= k && k <= 1e9);
        int p = k;
        for (int i = 2; i * i <= k; i++) {
            if (k % i == 0) {
                p = i;
        if (p == 1) {
            cout << "Alice" << endl;
            cout << n << endl;
            n -= n;
        } else if (n % p == 0) {
            cout << "Bob" << endl;
        } else {
            cout << "Alice" << endl;
            cout << n % p << endl;
            n -= n % p;
        while (true) {
            cin >> n;
            if (n == 0) {
            } else if (n == -1) {
            cout << n % p << endl;
            n -= n % p;
    cerr << sn << endl;
    assert(sn <= 1e6);
    return 0;
Editorialist's code (Python)
for _ in range(int(input())):
    n, k = map(int, input().split())
    if k == 1:
    p = k
    for x in range(2, k+1):
        if x*x > k: break
        if k%x == 0:
            p = x
    if n%p == 0:
        n -= n%p
    while n > 0:
        n = int(input())
        n -= n%p
1 Like

Is this a hack? I do naive quadratic dp with cutoffs.


hi , can you explain your approach.

A naive quadratic solution is to do dynamic programming to determine the winning step (if it exists) for every 1 <= i <= n. It is quadratic because for each i you have to try every 1 <= x <= i such that gcd(k, x) = 1. If i - x is a losing position then i is a winning position. I try only the first few xs to speed up the solution. I also try x = i first since it is a winning step for all i such that gcd(i, k) = 1.

1 Like

Unfortunately, yes, this shouldn’t have passed.

A countertest is N = 66799 and K = 988027, your code chooses to play as Bob but Alice can win.

1 Like

Why did you used this condition?
xs.size() <= 10'000'000 / n

I wonder how did you come up with such a countertest :thinking:
How did you figure out that kind of specific testcase?