我用了一个类似筛法的方式通过了这道题。

原理是因为如果一个数不可能成为答案那么它的倍数也不会成为答案。

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;
#define int long long
#define N 1000010
int n,k,a[N],f[N][21],pos[N][21],lg[N];
bool fl[N];
int ask(int l,int r){
    int k=lg[r-l+1];
    return f[l][k]>f[r-(1<<k)+1][k]?pos[l][k]:pos[r-(1<<k)+1][k];
}
int calc(int l,int r,int x){
    int ps=ask(l,r);
    if(a[ps]%x==0){
        int s=1;
        if(ps>l){
            s+=calc(l,ps-1,x);
        }
        if(ps<r){
            s+=calc(ps+1,r,x);
        }
        return s;
    }
    int maxn=0;
    if(l>1&&(ps<r)){
        maxn=max(maxn,calc(ps+1,r,x));
    }
    if(r<n&&(ps>l)){
        maxn=max(maxn,calc(l,ps-1,x));
    }
    return maxn;
}
signed main(){
    cin>>n>>k;
    lg[0]=-1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i][0]=a[i];
        pos[i][0]=i;
        lg[i]=lg[i>>1]+1;
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            if(f[i][j-1]>f[i+(1<<(j-1))][j-1]){
                pos[i][j]=pos[i][j-1];
            }
            else{
                pos[i][j]=pos[i+(1<<(j-1))][j-1];
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(!fl[i]){
            int sum=calc(1,n,i);
            if(sum<k){
                for(int j=i;j<=1000000;j+=i){
                    fl[j]=1;
                }
            }
        }
    }
    for(int i=1000000;i;i--){
        if(!fl[i]){
            cout<<i;
            return 0;
        }
    }
}

在最坏的测试点上用时288ms。

在数据全为 997920 时，代码表现最差，clac(1,n,i) 运行了 78737 次，当n=100000 时，代码会超时。

故请求添加hack