3000ms

Difficulty: 8

所属公司 : 科大讯飞

时间 :2025年8月9日

算法与标签>双指针

会员或题库专享

请先，开通会员或购买题库科大讯飞机考编程题库，可解锁完整内容。

购买科大讯飞机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（科大讯飞机考编程题库），可解锁完整内容。

购买题库开通会员

思路

关键等价

设整体 LCM 的质因数分解为

\text{LCM}(a_1,\dots,a_n)=\prod_{p} p^{E_p},

题目内容

给定一个长度为n的正整数数组 $a_1，a_2,...,a_n$ 。你需要找到一个连续子数组 $[1,r]$ ，使得该子数组的最小公倍数 $(LCM)$ 等于整个数组的 $LCM$ ，并且该子数组的长度尽可能短。

请输出满足条件的子数组的最小长度。