取数游戏

取数游戏

测试数据来自 wjszez/2173

lqp刚学了辗转相除法,正不亦乐乎。will 又出来捣乱,给lqp 留了个难题。
给 N 个数,用 a1,a2…an来表示。现在will 让lqp依次取数,第一个数可以随意取。假使目前取得 aj,下一个数取ak(k>j),则ak必须满足gcd(aj,ak)≥L。 到底要取多少个数呢?自然是越多越好!
不用多说,这不仅是给lqp的难题,也是给你的难题。
输入
第一行包含两个数N 和 L.
接下来一行,有 N 个数用空格隔开,依次是 a1,a2…an.
输出
仅包含一行一个数,表示按上述取法,最多可以取的数的个数。
样例输入
5 6
7 16 9 24 6
样例输出
3
Hint
选取 3个数16、24、6。gcd(16,24)=8,gcd(24,6)=6。
2≤L≤ai≤1 000 000;
30% 的数据N≤1000;
100% 的数据 N≤50 000

信息

ID
2581
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者