思路

反过来想，就是要从这个序列中选取n - k 个数的子序列，使得两两成倍数。

我们对序列排序之后，<两两成倍数> 这个性质具有同样的子问题。

比如x , y , z 符合这个性质，那么只要w > z 并且 w 是z的倍数。

这种情况下， x , y , z , w 也满足<两两成倍数>的性质。

题目内容

一位作曲家创作了一段旋律，用 $n$ 个音符的频率表示，第 $i$ 个音符的频率为 $a_i$。

如果一段旋律中任意两个音符的频率，其中一个都是另一个的整数倍，则称这段旋律是“和谐”的。特别地，一段空的旋律或只包含一个音符的旋律也视为和谐的。

作曲家希望恰好删去 $k$ 个音符，使得剩下的旋律是和谐的。他想知道有多少种不同的删除方案。两种方案视为不同，当且仅当剩下的音符集合不同。

数据范围：音符数量 $n$ 满足 $1 \le n \le 10^3$，删去的数量 $k$ 满足 $1 \le k \le n$。每个音符的频率 $a_i$ 为不超过 $10^9$ 的正整数，且初始所有频率两两不同。

输入描述

第一行包含两个整数 $n$ 和 $k$，分别表示音符总数和需要删去的音符数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个音符的频率。

输出描述

输出一个整数，表示不同的删除方案数。

样例1

输入

1 1
7

输出

1

说明

音符总数 n=1，需要删去 k=1 个音符，剩余 0 个音符，即空旋律。题目规定空旋律也是和谐的，因此唯一的方案就是删去所有音符，方案数为 1。

样例2

输入

4 3
5 10 20 30

输出

4

说明

n=4，k=3，需要删去 3 个音符，剩余 1 个音符。根据定义，只包含一个音符的旋律是和谐的。因此任意一种删除方案，只要最终剩下的集合为 $\{5\}$、$\{10\}$、$\{20\}$ 或 $\{30\}$ 均符合要求。共有 4 种不同的剩余集合，故方案数为 4。

样例3

输入

4 2
1 2 3 6

输出

5

说明

n=4，k=2，剩余 2 个音符。符合条件的“和谐”对必须满足一个频率是另一个的整数倍。枚举所有对：

• $\{1,2\}$（2 是 1 的 2 倍）
• $\{1,3\}$（3 是 1 的 3 倍）
• $\{1,6\}$（6 是 1 的 6 倍）
• $\{2,6\}$（6 是 2 的 3 倍）
• $\{3,6\}$（6 是 3 的 2 倍） $\{2,3\}$ 不和谐，因为 2 和 3 互不为整数倍。因此共有 5 种方案。

样例4

输入

5 2
2 4 8 16 32

输出

10

说明

n=5，k=2，剩余 3 个音符。所有频率 $[2, 4, 8, 16, 32]$ 构成公比为 2 的等比数列，任意两个数都存在整数倍关系。因此，任意一个包含 3 个音符的子集都是和谐的。问题转化为从 5 个元素中选 3 个的组合数，即 $C(5,3) = 10$。故输出 10。