# 分析

(dp[i])表示前(i)个位置分完最多可以分多少段只要(dp[n]geq k)即合法。

# 代码

``````#include <cstdio>
#include <cctype>
#include <cmath>
#define rr register
using namespace std;
const int N=100011; int a[N],n,m,x,bl;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline signed max(int a,int b){return a>b?a:b;}
struct Descartes{
int st[N],ls[N],rs[N],top,last,root;
inline void build(){
top=0,last=0;
for (rr int i=1;i<=n;++i){
while (a[st[top]]<a[i]) --top;
if (top<last) ls[i]=st[top+1];
if (top) rs[st[top]]=i;
st[last=++top]=i;
}
root=st[1];
}
inline signed query(int now,int l,int r){
if (!now) return 0;
if (a[now]%x==0) return query(ls[now],l,now-1)+query(rs[now],now+1,r)+1;
rr int ans=0;
if (l>1) ans=max(ans,query(rs[now],now+1,r));
if (r<n) ans=max(ans,query(ls[now],l,now-1));
return ans;
}
}Tre;
signed main(){
n=iut(),m=iut();
for (rr int i=1;i<=n;++i) a[0]=max(a[0],a[i]=iut());
Tre.build(),bl=sqrt(a[0]);
for (rr int i=1;i<=bl;++i)
if (a[0]%i==0){
x=a[0]/i;
if (Tre.query(Tre.root,1,n)>=m)
return !printf("%d",x);
}
for (rr int i=bl;i;--i)
if (a[0]%i==0){
x=i;
if (Tre.query(Tre.root,1,n)>=m)
return !printf("%d",x);
}
return 0;
}
``````