{"problem":{"name":"「MYOI-R3」消消乐","description":{"content":"给定一个长度为 $n$ 的数列 $a$。 定义一次操作为选择三个整数 $x,y,z\\in[1,n]$，满足 $\\gcd(a_x,a_y)=a_z$ 且 $x,y,z$ 两两不同，接着消除 $a_z$（即之后的操作中不能再选择 $a_z$ 了）。 问经过若干次操作后可否消除数列 $a_1\\sim a_n$ 中的 $n-2$ 个数？","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10443"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的数列 $a$。\n\n定义一次操作为选择三个整数 $x,y,z\\in[1,n]$，满足 $\\gcd(a_x,a_y)=a_z$ 且 $x,y,z$ 两两不同，接着消除 $a_z$（即之后的操作中不能再选择 $a_z$ 了）。\n\n问经过若干次操作后可否消除数列 $a_1\\sim a_n$ 中的 $n-2$ 个数？\n\n## Input\n\n第一行一个正整数 $T$，表示数据组数。\n\n对于每组数据，\n\n第一行一个正整数 $n$。\n\n第二行 $n$ 个正整数 $a_i$。\n\n## Output\n\n对于每组数据，一行一个字符串 `Yes` 或 `No`。\n\n[samples]\n\n## Background\n\n**upd 2024/5/12 18:14：增加了两组 Hack 数据，位于 Subtask 1，分值为 $0$ 分。**\n\n**upd 2024/5/12 21:27：增加了一组 Hack 数据，位于 Subtask 1，分值为 $0$ 分。**\n\n## Note\n\n### 样例解释：\n\n- 对于第一组数据，可以通过 $(2,3)$ 消除 $1$。\n- 对于第二组数据，可以证明无解。\n\n### 数据范围：\n\n本题共有 $20$ 个测试点，每个测试点的分值均为 $5$ 分。\n\n对于 $100\\%$ 的数据，$1\\le T\\le 10^5$，$2\\leq n \\leq 10^6$，$2 \\le \\sum n\\le 10^6$，$1\\le a_i\\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10443","tags":["洛谷原创","O2优化","最大公约数 gcd","洛谷月赛"],"sample_group":[["2\n3\n1 2 3\n3\n1 2 4","Yes\nNo"]],"created_at":"2026-03-03 11:09:25"}}