P8799蓝桥杯 2022 国 B] 齿轮

oscar0866 · 2023-07-23 12:53:26 · 题解

这道题还是有点难度滴。由题目可以推出：相邻齿轮的线速度相同，可以推出第一个齿轮和最后一个齿轮的线速度也是相同的。

思路：

对于每个齿轮半径，判断该半径值的所有约数是否为齿轮半径，如果是就将他俩的商标记。

AC 代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
const int N=200005;
int n,q,t;
int st[N];
int a[N],flag[N];   //flag 存当前数组中的数能构成哪些商值，作为 qi 
int main()
{
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        st[t]=1;
        a[i]=t;
    }
    //标记数组中任意两个数的商值，分解每个数的约数，将在数组中的约数标记为 1 就行 
    for(int i=1;i<=n;i++)
    {
        int up=sqrt(a[i]);

        for(int j=1;j<=up;j++)
        {
            if(a[i]%j==0) 
            {
                //j在数组里，则商就标记为 1 
                if(st[j])  flag[a[i]/j]=1;
                if(st[a[i]/j])   flag[j]=1;
            }
        }
    }
    for(int i=0;i<q;i++)
    {
        scanf("%d",&t);
        if(flag[t]) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}