题目

题目描述

小 Z 最近沉迷某款自走棋游戏，该游戏最近开启了 "符文大陆" 版本。该版本游戏开始前，会随机抽签选择一个城邦，每个城邦都有不同的效果，在每回合游戏中玩家通过将各种棋子放到棋盘上组成强有力的羁绊，每一种羁绊都会有不同的效果。

在某局游戏中，欧皇小 Z 组成了一个非常强大的阵容，该阵容的效果是在每回合游戏中，会召唤 $n$ 个法术，法术编号为 $1,2,\dots,n$，其中第 $i$ 个法术有一个能力值 $a_i$。棋盘位置从 $1$ 开始顺序编号，能力值为 $a_i$ 的法术，可以保护所有编号满足 $x | a_i$ 的 $x$ 位置，其中 $x|a_i$ 表示 $x$ 整除 $a_i$，即 $x$ 是 $a_i$ 的因数。

• 例如，如果某一个法术 $a_i=12$，那么这个保护法术就可以保护 $1,2,3,4,6,12$ 这些位置。

小 Z 想要 "吃鸡"（得到第一名），他通过计算得到，游戏的每一个回合，他都需要将最厉害的棋子放在至少被 $m$ 个法术所保护的位置。同时，为了尽可能得接近对手的棋子，小 Z 又需要将这个棋子放在编号尽可能大的位置。

小 Z 想要知道棋子应该放在什么位置。

【注意】

两个法术保护的位置可能完全相同，即 $n$ 个法术中，有可能存在多个法术，他们的能力值是一样的。

输入格式

第一行两个整数 $n,m$，整数间用空格隔开。

接下来一行，$n$ 个整数 $a_1,a_2,\dots,a_n$，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个法术的能力值。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

3 2
3 4 5

样例输出 #1

1

样例 #2

样例输入 #2

5 3
3 6 4 8 12

样例输出 #2

4

提示

【样例 1 解释】

法术 $1$ 的能力值为 $3$，可以保护位置 $1,3$；
法术 $2$ 的能力值为 $4$，可以保护位置 $1,2,4$；
法术 $3$ 的能力值为 $5$，可以保护位置 $1,5$；
其中，至少被 $2$ 个法术保护的位置只有 $1$，所以答案为 $1$。

【样例 2 解释】

法术 $1$ 的能力值为 $3$，可以保护位置 $1,3$；
法术 $2$ 的能力值为 $6$，可以保护位置 $1,2,3,6$；
法术 $3$ 的能力值为 $4$，可以保护位置 $1,2,4$；
法术 $4$ 的能力值为 $8$，可以保护位置 $1,2,4,8$；
法术 $5$ 的能力值为 $12$，可以保护位置 $1,2,3,4,6,12$；
其中，至少被 $3$ 个法术保护的位置有 $1,2,3,4$，其中编号最大的为 $4$，所以输出答案 $4$。

【数据范围】

本题有 $20$ 个测试点，每个测试点 $5$ 分。

对于所有测试点，有 $1\le m \le n \le 5 \times 10^6,1 \le a_i \le 10^7$。各个测试点详细分布如下：

测试点	$n\le$	$m\le$	$a_i\le$
$1$	$20$	$1$	$100$
$2 \sim 4$	$20$	$20$	$100$
$5$	$1000$	$2$	$1000$
$6\sim 8$	$1000$	$1000$	$1000$
$9\sim 10$	$1000$	$1000$	$10^5$
$11\sim 14$	$10^5$	$10^5$	$10^5$
$15\sim 18$	$10^6$	$10^6$	$10^7$
$19\sim 20$	$3 \times 10^6$	$3 \times 10^6$	$10^7$

本人代码（70pts）

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5000005];
int cnt[10000005];
int ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	cin >> n >> m;
	int maxn = -1;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		maxn = max(maxn, a[i]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= sqrt(a[i]); j++)
		{
			if (!(a[i] % j))
			{
				cnt[j]++;
				cnt[a[i] / j]++;
			}
		}
	}
	
	for (int i = maxn; i >= 1; i--)
	{
		if (cnt[i] >= m)
		{
			cout << i << "\n";
			return 0;
		}
	}
	return 0;
}