WHU个人赛第二场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, a_{n-1}, \cdots, a_{n-i+1})$

 #include<cstdio>

 using namespace std;

 const int maxn =  + ;

 int n, num[maxn], a[maxn], b[maxn];

 int gcd(int a, int b)

 {

     return b ==  ? a : gcd(b, a % b);

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d", &n);

         for(int i = ;i < n;i++)  scanf("%d", &num[i]);

         a[] = num[];

         for(int i = ;i < n;i++)  a[i] = gcd(num[i], a[i-]);

         b[] = num[n - ];

         for(int i= n-;i >= ;i--)  b[n -  - i] = gcd(num[i], b[n- i - ]);

         int ans = -;

         if(a[n-] > ans)  ans = a[n-];

         if(b[n-] > ans)  ans = b[n-];

         for(int i = ;i < n-;i++)

         {

             int tmp = gcd(a[i-], b[n--i]);

             if(tmp > ans)  ans = tmp;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

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

题目

分析

最新文章

热门文章