蓝桥杯3525 公因数匹配 | 枚举+数学
题目传送门
这个题目是一个数学题，由于只需要找到存在大于1的公因数的两数，所以比较方便的做法是统计每一个数的（质）因数。可以通过筛法统计质因数降低复杂度，但是直接枚举因数也可以满足要求。使用字典记录每个因数出现的位置，由于记录下标的有序性，可以直接遍历得到i、j最小的组。
from collections import defaultdict
dic = defaultdict(list)
n = int(input())
a = list(map(int, input().split()))
for i in range(0, n):
for j in range(2, int(a[i]**0.5)+1):
if a[i] % j == 0:
dic[j].append(i+1)
dic[a[i]//j].append(i+1)
dic[a[i]].append(i + 1)
mini = 10**5+5
minj = 10**5+5
for it in dic.values():
if len(it) > 1:
if mini > it[0]:
mini = it[0]
minj = it[1]
elif mini == it[0]:
minj = min(it[1], minj)
print(mini, minj)
END✨