题解：P11010 『STA - R7』Divide and Merge Game
DYYqwq
·
·
题解
考虑到如果有任意一个数是 $> \frac{n}{m}$ 的，那 Bob 无论如何也无法取到 $= \frac{n}{m}$ 的集合。
为了尽量构造出 $> \frac{n}{m}$ 的数，Alice 会选择填 $k-1$ 个 $1$，以及剩下的她期望 $> \frac{n}{m}$ 的数。
于是得，在 $n - (k - 1) > \frac{n}{m}$ 时，Alice 一定能赢。（这里显然 $m$ 默认取 $n$ 的最小真因子）
然后考虑如果 Alice 无法做到上面那种情况，那就是说所有数都会 $\leq \frac{n}{m}$，怎么办。
考虑设当前最大数为 $x$，自然不会有其他数 $> 1$。因为如果有非 $1$ 的数那为什么不加在 $x$ 身上呢（以利于卡死 Bob）？
但是经过之前的分析发现，只要 Bob 取到最小的 $m$，我们就卡不死。
于是得，在 $n - (k - 1) \leq \frac{n}{m}$ 时，Bob 一定能赢。（这里 $m$ 取值同上）
于是预处理一下 $10^5$ 以内的质数，每次找一下最小的能整除的就可以。
简单想一下应该比 $O(T\sqrt{n})$ 小很多，于是就能过了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int prime[100010] , tot; bool flag[100000010];
void solve()
{
int n , k; scanf("%d%d" , &n , &k);
bool qwq = 0;
for(int i = 1 ; prime[i] * prime[i] <= n ; i ++)
{
if(n % prime[i] == 0)
{
int x = n / prime[i];
if(n - (k - 1) > x) printf("Alice\n");
else printf("Bob\n");
qwq = 1;
break;
}
}
if(!qwq) printf(n == k ? "Bob\n" : "Alice\n"); // 一个细节，n=k 时应当 Bob 赢，因为是全 1。
}
int main()
{
for(int i = 2 ; i <= 100000 ; i ++)
{
if(!flag[i]) prime[++ tot] = i;
for(int j = 1 ; j <= tot ; j ++)
{
int nxt = i * prime[j];
if(nxt > 100000) break;
flag[nxt] = 1;
if(i % prime[j] == 0) break;
}
}
int T; scanf("%d" , &T);
while(T --) solve();
return 0;
}
```