Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-齿轮
题目 2699:

蓝桥杯2022年第十三届决赛真题-齿轮

时间限制: 1s 内存限制: 256MB 提交: 810 解决: 182

题目描述

这天,小明在组装齿轮。

他一共有 n 个齿轮,第 i 个齿轮的半径为 ri,他需要把这 n 个齿轮按一定顺序从左到右组装起来,这样最左边的齿轮转起来之后,可以传递到最右边的齿轮,并且这些齿轮能够起到提升或者降低转速 (角速度) 的作用。

蓝桥杯2022年第十三届决赛真题-齿轮

小明看着这些齿轮,突然有 Q 个疑问:能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 qi 倍?

输入格式

输入共 Q + 2 行,第一行为两个正整数 n, Q,表示齿轮数量和询问数量。

第二行为 n 个正整数 r1,r2, ...,rn,表示每个齿轮的半径。

后面 Q 行,每行一个正整数 qi 表示询问。

输出格式

Q 行,对于每个询问,如果存在至少一种组装方案满足条件,输出 ‘YES‘,否则输出 ‘NO‘。

样例输入

5 3
4 2 3 3 1
2
4
6

样例输出

YES
YES
NO

提示

询问 1 方案之一:2 3 3 4 1 。

询问 2 方案之一:4 2 3 3 1 。

询问 3 没有方案。

对于 15% 的数据,保证 n, Q ≤ 100 ;

对于 30% 的数据,保证 n, Q ≤ 2000 ;

对于 100% 的数据,保证 n, Q ≤ 2 × 105 ; ri , qi ≤ 2 × 105

标签