flash源码网站,宁晋网站建设设计,lnmp 安装 wordpress,邯郸公司做网站正题
题目链接:https://www.luogu.com.cn/problem/P7244?contestId38911 题目大意 nnn个数字#xff0c;分成连续非空的kkk段要求每一段的最大值的gcdgcdgcd最大。 解题思路
首先答案一定是最大值的约数#xff0c;这些数不多我们可以枚举这些数xxx。然后我们称xxx的倍数的…正题
题目链接:https://www.luogu.com.cn/problem/P7244?contestId38911 题目大意
nnn个数字分成连续非空的kkk段要求每一段的最大值的gcdgcdgcd最大。 解题思路
首先答案一定是最大值的约数这些数不多我们可以枚举这些数xxx。然后我们称xxx的倍数的位置为关键点。
现在我们要求在选取的全都是关键点的情况下最多能够选取的关键点数量
我们先找出最大的数第一次肯定是最大的那个数然后如果这个数是xxx的倍数就递归左右两边把数量加起来。如果不是我们就比较这个点和区间的左右两边一定是空的或者是关键点如果一边比这个数要大就可以递归另一边那一边的那个数区间延伸过来如果两边都比这个数要大就取两边的最大值即可。
RMQRMQRMQ维护区间最大的位置即可
时间复杂度O(nlognnamax)O(n\log nn\sqrt {a_{max}})O(nlognnamax) codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510,T20;
int n,m,a[N],f[N][T],lg[N],ans;
int rmq(int l,int r){int zlg[r-l1];return (a[f[l][z]]a[f[r1-(1z)][z]])?f[l][z]:f[r1-(1z)][z];
}
int calc(int l,int r,int pl,int pr,int x){if(lr)return 0;int krmq(l,r),tmp0;if(a[k]%x0)return calc(l,k-1,pl,a[k],x)calc(k1,r,a[k],pr,x)1;if(a[k]pr)tmpmax(tmp,calc(l,k-1,pl,pr,x));if(a[k]pl)tmpmax(tmp,calc(k1,r,pl,pr,x));if(a[k]pla[k]pr)return -1e9;return tmp;
}
void solve(int x){int krmq(1,n);if(calc(1,k-1,0,a[k],x)calc(k1,n,a[k],0,x)1m)ansmax(ans,x);return;
}
int main()
{scanf(%d%d,n,m);int w0;lg[0]-1;for(int i1;in;i){scanf(%d,a[i]);wmax(w,a[i]);f[i][0]i;lg[i]lg[i/2]1;}for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i){if(a[f[i][j-1]]a[f[i(1j-1)][j-1]])f[i][j]f[i][j-1];else f[i][j]f[i(1j-1)][j-1];}for(int i1;i*iw;i){if(w%i0){solve(i);if(i*i!w)solve(w/i);}}printf(%d\n,ans);return 0;
}
