# REMOVESTONES - Editorial

Author: coderdhanraj
Tester: tabr
Editorialist: iceknight1093

2968

Observation

# PROBLEM:

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.

# EXPLANATION:

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.

# TIME COMPLEXITY

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

# CODE:

Author's code (C++)
#include<bits/stdc++.h>
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;
return;
}
for (int i = 2; i <= sqK; i++) if (k % i == 0){
x = i;
break;
}
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"
#else
#define debug(...)
#endif

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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;
break;
}
}
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) {
break;
} else if (n == -1) {
assert(false);
}
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:
print('Alice')
print(n)
input()
continue

p = k
for x in range(2, k+1):
if x*x > k: break
if k%x == 0:
p = x
break

if n%p == 0:
print('Bob')
else:
print('Alice')
print(n%p)
n -= n%p

while n > 0:
n = int(input())
print(n%p)
n -= n%p
input()

1 Like

Is this a hack? https://www.codechef.com/viewsolution/99263224. I do naive quadratic dp with cutoffs.

2 Likes

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 How did you figure out that kind of specific testcase?