PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: coderdhanraj
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
2968
PREREQUISITES:
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:
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()
