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

解题思路:

通过列出算式 q=a₁/a₂*a₂/a₃*a₃......a_n-2/a_n-1*a_n-1/a_n

发现可以约掉中间部分只剩下头尾得到q=a₁/a_n

阅读题目发现q为整数,那么可得 a₁%a_n=0且a₁>=a_n，那么我们只要一遍每个齿轮半径的约数是否是另一个齿轮半径就可得到一个可行的q

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int a[200005];
map<int,bool>ma;
vector<int>v[200005];
bool hx[200005];
bool cmp(int a,int b)
{
	return a>b;
}
void f()
{
	for(int i=2;i<=200000;i++)
	{
		for(int j=i+i;j<=200000;j+=i)
		{
			v[j].push_back(i);
		}
	}
}
int main()
{
	int n,q;
	cin>>n>>q;
	f();//预处理约数
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		hx[a[i]]=1;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==a[i+1])ma[1]=1;//有两个相同齿轮则q可以为1
		if(hx[1]&&a[i]!=1)ma[a[i]]=1;//没预处理1,这里特判一下
		for(int j=0;j<v[a[i]].size();j++)
		{
			//cout<<1;
			if(hx[v[a[i]][j]])
			{
				ma[a[i]/v[a[i]][j]]=1;
			}
		}
	}
	while(q--)
	{
		int x;
		scanf("%d",&x);
		if(ma[x])
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}