1000ms

Difficulty: 8

所属公司 : 科大讯飞

时间 :2025年8月23日

算法与标签>数学

会员或题库专享

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

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

会员专享

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

购买题库开通会员

题解思路

结论

设 cover[p] 为数组里被质数 p 整除的元素个数（计重），则最长长度
$L=\max_{p\ \text{为质数}} \text{cover}[p]$

题目内容

Tk 有一个长度为 $n$ 的序列 $a_1,a_2,…,a_n$ ，Tk 希望选择一个最大公约数不为 $1$ 的子序列进行染色，但是他还想选择的子序列长度尽可能大，Tk 找到了你，希望你告诉他可以选择染色的最长子序列长度，并告诉他这种最长的可染色子序列总共有多少种。

如果两个子序列所包含的元素值的多重集合相同，则认为它们是同一种方案(即，不区分下标位置，仅按所含数字及出现次数判断是否相同)。