1.齿轮

1.题目描述

这天, 小明在组装齿轮。

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

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

2.输入格式

输入共 Q+2Q+2Q+2 行, 第一行为两个正整数 n,Qn,Qn,Q, 表示齿轮数量和询问数量。
第二行为 nnn 个正整数 r1,r2,…,rnr_{1}, r_{2}, \ldots, r_{n}r1,r2,…,rn, 表示每个齿轮的半径。后面 QQQ 行, 每行一个正整数 qiq_{i}qi表示询问。

3.输出格式

QQQ 行, 对于每个询问, 如果存在至少一种组装方案满足条件, 输出 ′YES′\mathrm{'YES}'′YES′, 否则输出 ’ NO\mathrm{NO}NO '。

4.样例输入

5 3
4 2 3 3 1
2
4
6

5.样例输出

YES
YES
NO

6.样例说明

询问 1 方案之一： 23341：23341
询问 2 方案之一：42331

询问 3 没有方案

6.数据范围

n,Q≤2×105;ri,qi≤2×105n,Q≤2×10^5 ;r i ,q i ≤2×10^5n,Q≤2×105;ri,qi≤2×105

7.原题链接

齿轮

2.解题思路

首先，这里涉及到一个物理公式，涉及到线速度v,v,v,角速度 www 以及半径 rrr 之间的关系。它们之间满足:
v=w∗rv=w*rv=w∗r

而齿轮模型是一个经典的物理模型，所有的齿轮的线速度都一样。 对于任意的齿轮之间都一定满足:
wx∗rx=wy∗ryw_x*r_x=w_y*r_ywx∗rx=wy∗ry

假设最左边的的齿轮半径为 xxx ，最右边的齿轮半径为 yyy ，那么使得最右边的齿轮的转速(角速度)是最左边的 qqq 倍，则需满足：
wx∗q=wyw_x*q=w_ywx∗q=wy
联立上述两式可解得：
rx=q∗ryr_x=q*r_yrx=q∗ry

所以我们可知，我们只需要去判断所有齿轮的半径之间是否存在两个齿轮的半径是 qqq 倍的关系。既然存在倍数关系，那么说明两个齿轮的半径其中一个必然是另外一个的因数。我们使用数组st，其中st[[i]表示是否有半径相差qqq倍的两个齿轮。

我们可以将齿轮半径按从小到大进行排序，对于每个齿轮的半径rir_iri，我们将去分解其所有的因数,如果存在某个数xxx是rir_iri的因数，并且之前已经出现过半径为xxx的齿轮，则说明当q=ri/xq=r_i/xq=ri/x时，我们是可以完成要求的。当然我们在分解因数时，应该进行优化，当xxx是rir_iri的因数时，ri/xr_i/xri/x也一定是rir_iri的因数，此时我们可以直接一起进行判断。这样分解每个数的复杂度的O(n)O(n)O(n)级别降低到O(n)O(\sqrt n)O(n)。

每次判断一个数后我们将其放入set中，在判断该数的因数在是否出现也是看set中是否存在。因为每个数的因数一定小于等于数的本身，所以这是我们排序的目的，确保了如果一个数的因数存在，那么一定会在它之前出现。

这个题目一定要注意一个点，齿轮的个数可能只有一个，那么此时左齿轮恰好就是右齿轮，如果查询的qqq为1时，是符合要求的，所以我们需要对这种情况进行特判。

时间复杂度：O(nn)O(n\sqrt n)O(nn)

3.Ac_code

#include
using namespace std;
typedef long long LL;
const int N=200010;bool st[N];
int r[N];
int main() 
{int n,q;scanf("%d%d",&n,&q);unordered_set s;for(int i=0;iscanf("%d",&r[i]);}sort(r,r+n);for(int i=0;iint v=r[i];for(int i=1;i<=v/i;++i){if(v%i==0){//存在这个半径为i的齿轮if(s.find(i)!=s.end()){st[v/i]=true;}//存在这个半径为v/i的齿轮if(s.find(v/i)!=s.end()){st[i]=true;}}}s.insert(r[i]);}for(int i=0;iint h;scanf("%d",&h);if(n==1&&h==1) puts("YES");else if(st[h]) puts("YES");else puts("NO");}return 0;
}

上一篇：充分利用时间

下一篇：VapSR

第十三届蓝桥杯C++B组国赛I题——齿轮 (AC)

目录