[蓝桥杯 2022 国 B] 齿轮

Luogu
IDLGP8799
Time1000ms
Memory128MB
DifficultyP3
2022数论蓝桥杯国赛
这天,小明在组装齿轮。 他一共有 $n$ 个齿轮,第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来,这样最左边的齿轮转起来之后,可以传递到最右边的齿轮,并且这些齿轮能够起到提升或者降低转速(角速度)的作用。 ![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_8ee8d95d6d0319bca20dg-17.jpg) 小明看着这些齿轮,突然有 $Q$ 个疑问: 能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 $q_{i}$ 倍? ## Input 输入共 $Q+2$ 行,第一行为两个正整数 $n, Q$, 表示齿轮数量和询问数量。 第二行为 $n$ 个正整数 $r_{1}, r_{2}, \ldots, r_{n}$,表示每个齿轮的半径。 后面 $Q$ 行,每行一个正整数 $q_{i}$ 表示询问。 ## Output $Q$ 行,对于每个询问,如果存在至少一种组装方案满足条件,输出 `YES`, 否则输出 `NO`。 [samples] ## Note **【样例说明】** 询问 $1$ 方案之一:`23341`。 询问 $2$ 方案之一:`42331`。 询问 $3$ 没有方案。 **【评测用例规模与约定】** 对于 $15 \%$ 的数据,保证 $n, Q \leq 100$; 对于 $30 \%$ 的数据,保证 $n, Q \leq 2000$; 对于 $100 \%$ 的数据,保证 $n\ge 2,n, Q \leq 2 \times 10^{5} ; a_{i}, q_{i} \leq 2 \times 10^{5}$。 蓝桥杯 2022 国赛 B 组 I 题。
Samples
Input #1
5 3
4 2 3 3 1
2
4
6
Output #1
YES
YES
NO
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯 2022 国 B] 齿轮",
    "description": {
      "content": "这天,小明在组装齿轮。 他一共有 $n$ 个齿轮,第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来,这样最左边的齿轮转起来之后,可以传递到最右边的齿轮,并且这些齿轮能够起到提升或者降低转速(角速度)的作用。 ![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanq",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8799"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "这天,小明在组装齿轮。\n\n他一共有 $n$ 个齿轮,第 $i$ 个齿轮的半径为 $r_{i}$, 他需要把这 $n$ 个齿轮按一定顺序从左到右组装起来,这样最左边的齿轮转起来之后,可以传递到最右边的齿轮,并且这些齿轮能够起到提升或者降低转速(角速度)的作用。\n\n![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanq...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments