#P1761. 最大子集
最大子集
题目描述
一个集合有 个互不相同的整数,另外给定一个正整数 ,定义两个整数 ( ) 不冲突的条件为, 。
请求出该集合的最大子集,要求子集中的元素互不冲突。
输入
第一行给定两个数 和 ( , )。
接下来一行包含 个不同正整数 ( )。
输出
输出最大互不冲突子集的数量。
样例
4 2
1 2 3 4
3
一个集合有 N 个互不相同的整数,另外给定一个正整数 T ,定义两个整数 x,y ( x≤y ) 不冲突的条件为, y=T×x 。
请求出该集合的最大子集,要求子集中的元素互不冲突。
第一行给定两个数 N 和 T ( 1≤N≤105, 1≤T≤109 )。
接下来一行包含 N 个不同正整数 ai ( 1≤ai≤109 )。
输出最大互不冲突子集的数量。
4 2
1 2 3 4
3