P3454.第2题-子序列染色
题目内容
Tk 有一个长度为 n 的序列 a1,a2,…,an ，Tk 希望选择一个最大公约数不为 1 的子序列进行染色，但是他还想选择的子序列长度尽可能大，Tk 找到了你，希望你告诉他可以选择染色的最长子序列长度，并告诉他这种最长的可染色子序列总共有多少种。
如果两个子序列所包含的元素值的多重集合相同，则认为它们是同一种方案(即，不区分下标位置，仅按所含数字及出现次数判断是否相同)。
【名词解释】
最大公约数(gcd)，指多个整数共有约数中最大的一个。例如，12、18 和 30 的公约数有 1,2,3,6 ，其中最大的约数是 6 ，因此 gcd(12,18,30)=6 。
子序列：从原序列中删除任意个(可以为零，也可以为全部)元素后，保持剩余元素相对顺序不变得到的新序列。
输入描述
第一行输入一个整数 n(1≤n≤2×106) 表表示序列长度。
第二行输入 n 个整数
a1,a2,…,an(1≦ai≤2×106) 表示序列 a ，
题目保证序列 a 中的元素不全为 1 。
输出描述
输出两个整数，其中第一个整数表示子序列长度,第二个整数表示子序列个数。
样例1
输入
6
2 4 3 9 7 35
输出
2 3
说明
满足条件的最长子序列有 {2,4 }, { 3,9 }, { 7,35 } 。
