You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
小美有一个长度为 n 的数组 a ,他希望删除恰好 k 个数,使得这个数组是一个倍数数组。
倍数数组是指数组中任意两个数 a 和 b 都是倍数关系,要么 a 是 b 的倍数,要么 b 是 a 的倍数。
特别地,长度为 1 和 0 的数组也是倍数数组
现在,小美想问你有多少种不同的删除方案。
第一行,两个整数 n,k((1≤k≤n≤103) 分别表示数组的长度,以及要删除的数的数量。
第二行,n 个整数表示数组 a,第 i 个数为 ai(1≤ai≤109) 。
数据保证初始的数组 a 中数两两不同。
一个整数,表示不同的删除方案。
输入
3 1
1 2 4
输出
3
说明
方案1:删除 1
。
方案2:删除 2
。
方案3:删除 4
。
反过来想,就是要从这个序列中选取n - k 个数的子序列,使得两两成倍数。
我们对序列排序之后,<两两成倍数> 这个性质具有同样的子问题。
比如x , y , z 符合这个性质,那么只要w > z 并且 w 是z的倍数。
这种情况下, x , y , z , w 也满足<两两成倍数>的性质。