首页 > 代码库 > hdu 6025 Coprime Sequence (前后缀GCD)
hdu 6025 Coprime Sequence (前后缀GCD)
题目链接:hdu 6025 Coprime Sequence
题意:
给你n个数,让你删掉一个数,使得剩下的数的gcd最大
题解:
先将这一列数的前缀后缀gcd预处理一下。
然后挨着for一下就行了
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=1e5+7; 6 int t,pre[N],suf[N],n,a[N]; 7 8 int main() 9 { 10 scanf("%d",&t); 11 while(t--) 12 { 13 scanf("%d",&n); 14 F(i,1,n)scanf("%d",a+i); 15 pre[1]=a[1],suf[n]=a[n]; 16 F(i,2,n)pre[i]=__gcd(pre[i-1],a[i]); 17 for(int i=n-1;i>0;i--)suf[i]=__gcd(suf[i+1],a[i]); 18 int mx=0; 19 F(i,2,n-1)mx=max(mx,__gcd(pre[i-1],suf[i+1])); 20 mx=max(pre[n-1],mx),mx=max(suf[2],mx); 21 printf("%d\n",mx); 22 } 23 return 0; 24 }
hdu 6025 Coprime Sequence (前后缀GCD)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。