D. 第4题-小美的倍数数组

第4题-小美的倍数数组

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.

题目描述

小美有一个长度为 nn 的数组 aa ,他希望删除恰好 kk 个数,使得这个数组是一个倍数数组。

倍数数组是指数组中任意两个数 aabb 都是倍数关系,要么 aabb 的倍数,要么 bbaa 的倍数。

特别地,长度为 1100 的数组也是倍数数组

现在,小美想问你有多少种不同的删除方案。

输入描述

第一行,两个整数 n,k((1kn103)n,k((1 \leq k \leq n \leq 10^3) 分别表示数组的长度,以及要删除的数的数量。
第二行,nn 个整数表示数组 aa,第 ii 个数为 ai(1ai109)a_i(1 \leq a_i \leq 10^9)

数据保证初始的数组 aa 中数两两不同。

输出描述

一个整数,表示不同的删除方案。

样例

输入

3 1
1 2 4

输出

说明

方案1:删除 1
方案2:删除 2
方案3:删除 4

秋招模拟赛第37场|2023.09.02-美团

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2023-9-4 19:00
End at
2023-9-4 21:00
Duration
2 hour(s)
Host
Partic.
42