WHU个人赛第二场C——前缀和&&后缀和
发布时间：2020-12-16 07:19:18 所属栏目：百科 来源：网络整理
导读：题目 链接 题意：给定 $n$ 个整数，去掉其中一个数使得剩下数字的gcd最大，求最大的gcd.($3 leq n leq 100000$) 分析 枚举每一个位置，显然每次枚举都计算所有数的gcd存在大量的重复计算，所以先计算出gcd前缀和gcd后缀。$pre _ gcd[i] = gcd(a_1,a_2,cd
题目链接 题意：给定 $n$ 个整数，去掉其中一个数使得剩下数字的gcd最大，求最大的gcd.($3 leq n leq 100000$) 分析枚举每一个位置，显然每次枚举都计算所有数的gcd存在大量的重复计算，所以先计算出gcd前缀和gcd后缀。$pre _ gcd[i] = gcd(a_1,a_2,cdots,a_i),? suf _ gcd[i] = gcd(a_n,a_{n-1},a_{n-i+1})$ 1 #include<cstdio> 2 using namespace std; 3 4 const int maxn = 100000 + 10; 5 int n,num[maxn],a[maxn],b[maxn]; 6 7 int gcd(int a,int b) 8 { 9 return b == 0 ? a : gcd(b,a % b); 10 } 11 12 int main() 13 { 14 int T; 15 scanf("%d",&T); 16 while(T--) 17 { 18 scanf("%d",&n); 19 for(int i = 0;i < n;i++) scanf("%d",&num[i]); 20 21 a[0] = num[0]; 22 for(int i = 1;i < n;i++) a[i] = gcd(num[i],a[i-1]); 23 b[0] = num[n - 1]; 24 for(int i= n-2;i >= 0;i--) b[n - 1 - i] = gcd(num[i],b[n- i - 2]); 25 26 int ans = -1; 27 if(a[n-2] > ans) ans = a[n-2]; 28 if(b[n-2] > ans) ans = b[n-2]; 29 for(int i = 1;i < n-1;i++) 30 { 31 int tmp = gcd(a[i-1],b[n-2-i]); 32 if(tmp > ans) ans = tmp; 33 } 34 printf("%dn",ans); 35 } 36 return 0; 37 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |