「DROI」Round 1 游戏

Luogu

IDLGP8980

Time1000ms

Memory512MB

DifficultyP5

数学洛谷原创O2优化素数判断,质数,筛法

你将和一名小朋友进行 $T$ 次游戏，每一次游戏的规则如下： 1. 首先，你需要在 $[1,n]$ 中选择一个正整数 $x$。 2. 接下来，小朋友会有 $Q$ 次询问，对于每次询问，他会给出一个 $a_i$（保证 $a_i \in [1,n]$），你需要回答他 $\gcd(x,a_i)$ 的值。 3. 当某一轮小朋友得到答案后，如果他能唯一确定你选择的数，那么本次游戏结束。现在**你提前知道了**小朋友每次询问的 $a_i$，你需要找到一个 $x$，使得游戏持续的轮数最长。 ## Input **本题有多组数据。** 第一行一个整数 $T$，表示进行游戏的次数。对于每次游戏：第一行两个整数，分别为 $n$ 和 $Q$。第二行 $Q$ 个整数，其中第 $i$ 个整数表示 $a_i$。 ## Output 对于每次游戏，请输出游戏能持续的最长轮数，如果存在一个 $x$ 使得小朋友在 $Q$ 轮之后也无法唯一确定其值，则输出`game won't stop`。 [samples] ## Background 人生，又何尝不是一场游戏呢？ ## Note #### 样例解释#1 选取 $11$ 作为 $x$，显然小朋友到游戏结束也无法唯一确定。 ------------ #### 样例解释#2 对于第一组数据：选取 $1$ 作为 $x$，小朋友在第五轮结束后可以唯一确定 $x$，可以证明不存在更优的 $x$。对于第二组数据：同理，选取 $1$ 作为 $x$ 即可。 ------------ #### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(20\%)$：$n,Q\leq 500$。 - $\operatorname{Subtask} 2(20\%)$：$n,Q \leq 5 \times 10^4$。 - $\operatorname{Subtask} 3(30\%)$：$Q \leq 10^5$。 - $\operatorname{Subtask} 4(30\%)$：无特殊限制。对于 $100\%$ 的数据：$T \leq 10$，$1 \leq a_i \leq n \leq 10^{18}$，$1 \leq Q \leq 2\times 10^{6}$，$\sum Q \leq 6\times 10^{6}$。 **本题输入量较大，请用较快的输入方法。**

Samples

Input #1

1
11 3
8 9 5

Output #1

game won't stop

Input #2

2
8 5
8 2 3 5 7 
24 16
3 17 18 5 19 4 16 23 7 11 13 18 6 21 22 2

Output #2

5
11

API Response (JSON)

{
  "problem": {
    "name": "「DROI」Round 1 游戏",
    "description": {
      "content": "你将和一名小朋友进行 $T$ 次游戏，每一次游戏的规则如下： 1. 首先，你需要在 $[1,n]$ 中选择一个正整数 $x$。 2. 接下来，小朋友会有 $Q$ 次询问，对于每次询问，他会给出一个 $a_i$（保证 $a_i \\in [1,n]$），你需要回答他 $\\gcd(x,a_i)$ 的值。 3. 当某一轮小朋友得到答案后，如果他能唯一确定你选择的数，那么本次游戏结束。 现在**你提",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8980"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你将和一名小朋友进行 $T$ 次游戏，每一次游戏的规则如下：\n\n1. 首先，你需要在 $[1,n]$ 中选择一个正整数 $x$。\n\n2. 接下来，小朋友会有 $Q$ 次询问，对于每次询问，他会给出一个 $a_i$（保证 $a_i \\in [1,n]$），你需要回答他 $\\gcd(x,a_i)$ 的值。\n\n3. 当某一轮小朋友得到答案后，如果他能唯一确定你选择的数，那么本次游戏结束。\n\n现在**你提...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments