3164: 蓝桥杯2023年第十四届省赛真题-公因数匹配

解题思路:

mmax存储结果左端点，mmin存储结果右端点，r存储当前数字左端点，l存储当前数字右端点

1.采用map数组记录数的因子以及出现的位置。

2.对于每个数字k,从2开始（题目要求）求它的因子j，去map中找是否已经存在：如果没有，则记录对应的编号；如果有并且不是当前编号，用r记录其编号（要取最小值，否则可能会覆盖前面的最小内容），l记录当前编号（当前编号固定不会影响结果），同时看k/j的情况，重复上述步骤。

3.最后看自身k的情况，重复上述步骤

4.遍历完数字之后，如果r比mmax小，说明左端点更新了，则更新存储结果的变量mmax；如果r相等但是l变小了，同样更新。

注意事项:

1.用map q找数字的话，找不到返回去q.end()

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n;
map<int,int>q;
int mmax=9999999;
int mmin=9999999;
int main(){
	cin>>n;
	int k;

	for(int i=1;i<=n;i++){
		cin>>k;
		int r=9999999;
		int l=0;
		int z=int(sqrt(k)+2);
		for(int j=2;j<=z;j++){//不遍历到k节省时间
			if(k%j==0&&k!=j){
				if(q.find(j)==q.end()){//没找到
					q[j]=i;//记录第一次位置 
				}
				else if(q[j]!=i){
					r=min(r,q[j]);
					l=i;
				} 
				if(q.find(k/j)==q.end()){//看因子k/j
					q[k/j]=i;
				}
				else if(q[k/j]!=i){
					r=min(r,q[k/j]);
					l=i;
				}
			}
		}
		if(q.find(k)==q.end()){//看自身因子k
			q[k]=i;
		}
		else if(q[k]!=i){
			r=min(r,q[k]);
			l=i;
		}
		if(r<mmax){//考虑更新
			mmax=min(r,mmax);
			mmin=l;
		}
		else if(r==mmax&&l<mmin){
			mmin=l;
			mmax=r;
		}
		
		
	}
	cout<<mmax<<" "<<mmin;
	
	
	
	
	return 0;
}