首页 > 代码库 > hdu 6025
hdu 6025
题意:t组,n个数,去掉任意一个数,使n-1个数的GCD最大
思路:求前缀gcd,后缀gcd,然后max(gcd(gcd(1,i),gcd(i+1,n)).
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 int a[100004]; 5 int b[100004]; 6 int c[100004]; 7 8 int main(){ 9 int t; 10 scanf("%d",&t); 11 while(t--){ 12 int n; 13 scanf("%d",&n); 14 for(int i=1;i<=n;i++) 15 scanf("%d",&a[i]); 16 b[1]=a[1]; 17 for(int i=2;i<=n;i++) 18 b[i]=__gcd(b[i-1],a[i]); 19 c[n]=a[n]; 20 for(int i=n-1;i>=1;i--) 21 c[i]=__gcd(c[i+1],a[i]); 22 int Max=c[2]; 23 for(int i=2;i<=n-1;i++) 24 Max=max(Max,__gcd(b[i-1],c[i+1])); 25 Max=max(Max,b[n-1]); 26 cout<<Max<<endl; 27 28 } 29 return 0; 30 }
hdu 6025
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。