WHU个人赛第二场C——前缀和&&后缀和_C

概述题目链接题意：给定 $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, 题目

链接

题意：给定 $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})$

@H_502_16@

 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("%d\n",ans);35     }36     return 0;37 }