如果你有收獲，請為這篇文章點個贊吧！

Description

求數(shù)組的第k小，數(shù)字?jǐn)?shù)量非常多。

Input

每組數(shù)據(jù)給出n m k表示有n個數(shù)，求第k小，數(shù)組的數(shù)字由以下規(guī)則得到：

ai?=?mi mod? (109+7),?i?=?1,?2,?...,?n

其中 1?≤?n,?m?≤?5?×?107, 1?≤?k?≤?n，數(shù)據(jù)保證得到的數(shù)組元素大部分互不相等。

Output

輸出第k小的數(shù)

Sample Input

3 2 2

Sample Output

4

Hint

先復(fù)習(xí)下快速排序的實現(xiàn)

實現(xiàn)代碼：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<cmath>
#include<complex>
#include<vector>
#include<algorithm>
const int mod = 1e9 + 7;
const int maxn = 1e8 + 10;
int n, m, k;
int a[maxn];
int GetK(int left, int right, int k)
{
    if(left == right - 1) return a[left];
    int low = left, high = right - 1, center = a[low];
    while(low < high)
    {
        while(low < high && a[high] >= center) high --;
        a[low] = a[high];
        while(low < high && a[low] <= center) low ++;
        a[high] = a[low];
    }
    a[low] = center;
    if(low - left >= k) return GetK(left, low, k);
    else if(low - left + 1 == k) return a[low];
    else return GetK(low + 1, right, k - (low - left) - 1);
}
int main()
{
    while(scanf("%d%d%d", &n, &m, &k) != EOF)
    {
        a[0] = m;
        for(int i = 1; i < n; i ++)
            a[i] = 1LL * a[i - 1] * m % mod;
        printf("%d\n", GetK(0, n, k));
    }
    return 0;
}