登录注册

快捷登录

分治-很大的数组的第K小

计算机软件开发 2024-10-8 10:30:16 86 0 来自中国

假如你有劳绩，请为这篇文章点个赞吧！

Description

求数组的第k小，数字数目非常多。
Input

每组数据给出n m k表现有n个数，求第k小，数组的数字由以下规则得到：
ai = mi mod (109+7), i = 1, 2, ..., n
此中 1 ≤ n, m ≤ 5 × 107, 1 ≤ k ≤ n，数据包管得到的数组元素大部分互不相等。
Output

输出第k小的数
Sample Input

3 2 2
Sample Output

4
Hint

先复习下快速排序的实现
实今世码：