人寿研发，第三题，大家讨论一下吗hhh
题目抽象一下，就是划分一个数组，使得数组被分出来的段数最小，要求每个被分出来的数组排序之后都是一个公差大于1等差数列的子序列；
我的想法是：
1.对于i-j之间的数据考虑排序之后是否可以是一个满足条件的等差数列，等差数列的判别我是这样做的：先排序，考虑：长度为1，True，长度为2判断不相邻就True，其余的，计算一下和这段数组中最小的的差值，然后对这个差值进行质因子分解，然后判断是否有相同的质因子（还应该判断一下是否有重复的元素，这个确实没考虑到，但是一个点都没过我觉得很过分），如果没有相同的质因子了，返回flase
2.然后做一次dfs，考虑每个元素成为开头或者加到之前的队尾中， 计算最少的组合；
想问问大佬们，这个思路为啥一个点都过不去；
def get_num(t):
s = set()
i = 2
while i**2 <= t:
if t%i==0:
s.add(i)
while t%i == 0:
t//=i
i += 1
if t!=1:
s.add(t)
return s
def if_same(nums):
if len(nums)<=1:
return True
nums.sort()
if len(nums) == 2 and nums[0]<nums[1]-1:
return True
start = nums[0]
s_start = get_num(nums[1]-nums[0])
for i in range(2,len(nums)):
s_i = get_num(nums[i]-nums[0])
if not (s_i & s_start) :
return False
s_start = s_i & s_start
return True
def dfs(idx,path,howmany):
global res
if idx>=len(data):
res = min(res,howmany)
return
path.append(data[idx])
if if_same(path):
dfs(idx+1,path,howmany)
dfs(idx+1,[data[idx]],howmany+1)
n = int(input())
data = list(map(int,input().split()))
res = float('inf')
dfs(0,[],1)
print(res) 
