{"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现在**你提前知道了**小朋友每次询问的 $a_i$，你需要找到一个 $x$，使得游戏持续的轮数最长。\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$，表示进行游戏的次数。\n\n对于每次游戏：\n\n第一行两个整数，分别为 $n$ 和 $Q$。\n\n第二行 $Q$ 个整数，其中第 $i$ 个整数表示 $a_i$。\n\n## Output\n\n对于每次游戏，请输出游戏能持续的最长轮数，如果存在一个 $x$ 使得小朋友在 $Q$ 轮之后也无法唯一确定其值，则输出`game won't stop`。\n\n[samples]\n\n## Background\n\n人生，又何尝不是一场游戏呢？\n\n## Note\n\n#### 样例解释#1\n\n选取 $11$ 作为 $x$，显然小朋友到游戏结束也无法唯一确定。\n\n------------\n\n#### 样例解释#2\n\n对于第一组数据：选取 $1$ 作为 $x$，小朋友在第五轮结束后可以唯一确定 $x$，可以证明不存在更优的 $x$。\n\n对于第二组数据：同理，选取 $1$ 作为 $x$ 即可。\n\n------------\n\n#### 数据范围\n\n**「本题采用捆绑测试」** \n\n- $\\operatorname{Subtask} 1(20\\%)$：$n,Q\\leq 500$。\n\n- $\\operatorname{Subtask} 2(20\\%)$：$n,Q \\leq 5 \\times 10^4$。\n\n- $\\operatorname{Subtask} 3(30\\%)$：$Q \\leq 10^5$。\n\n- $\\operatorname{Subtask} 4(30\\%)$：无特殊限制。\n\n对于 $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}$。\n\n**本题输入量较大，请用较快的输入方法。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8980","tags":["数学","洛谷原创","O2优化","素数判断,质数,筛法"],"sample_group":[["1\n11 3\n8 9 5","game won't stop"],["2\n8 5\n8 2 3 5 7 \n24 16\n3 17 18 5 19 4 16 23 7 11 13 18 6 21 22 2\n","5\n11\n"]],"created_at":"2026-03-03 11:09:25"}}