# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* coderdhanraj

*tabr*

**Tester:***iceknight1093*

**Editorialist:**# 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()
```