bzoj#P1978. [Beijing2010 组队] 取数游戏 game

[Beijing2010 组队] 取数游戏 game

题目描述

小 C 刚学了辗转相除法,正不亦乐乎,这小 P 又出来捣乱,给小 C 留了个难题。

给定 nn 个数,用 a1,a2,,ana_1,a_2, \ldots,a_n 来表示。现在小 P 让小 C 依次取数,其中第一个数可以随意取。假使目前取得 aja_j,下一个数取 aka_kk>jk>j),则 aka_k 必须满足 gcd(aj,ak)l\gcd(a_j,a_k) \ge l

到底要取多少个数呢?自然是越多越好!

不用多说,这不仅是给小 C 的难题,也是给你的难题。

输入格式

第一行包含两个数 nnll

接下来一行,有 nn 个数用空格隔开,依次是 a1,a2,,ana_1,a_2,\ldots,a_n

输出格式

仅包含一行一个数,表示按上述取法,最多可以取的数的个数。

5 6 
7 16 9 24 6
3

样例解释 1

选取 33 个数 16,24,616,24,6gcd(16,24)=8\gcd(16,24)=8gcd(6,24)=6\gcd(6,24)=6

数据规模与约定

  • 对于 30%30\% 的数据,n103n \le 10^3
  • 对于 100%100\% 的数据,n5×104n \le 5 \times 10^42lai1062 \le l \le a_i \le 10^6