题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6025

题意

互质序列是一个由n个正整数组成的序列，它们的gcd（最大公约数）等于1。
我们尝试通过只删除一个整数来最大化这些整数的gcd。现在给定一个序列，请最大化其元素的gcd。
输入
输入的第一行包含一个整数t（1≤t≤10），表示测试用例的数量。
在每个测试用例中，第一行有一个整数n（3≤n≤1e5），表示序列中的整数数。
然后下面的行由n个整数a1，a2，…，an（1≤ai≤1e9）组成，表示序列中的元素。
输出
对于每个测试用例，打印一个包含一个整数的单行，表示最大的GCD。

思路

其实就是暴力, 枚举每一种情况, 然后计算剩下的所有元素的gcd, 只不过总的来说, gcd重复计算太多导致TLE.
所以考虑被重复计算的数据: 一部分整数的gcd
因为多个整数求gcd的特殊性 (应该叫传递性?) 所以有了前缀gcd和后缀gcd

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100000 + 100;
int a[N],pre[N],suf[N];

int gcd( int a, int b ) { return b ? gcd(b,a%b) : a; }
int max( int a, int b ) { return a>b ? a : b; }

int main(void)
{
    int loop;
    cin >> loop;
    while(loop--)
    {
        memset(pre,0,sizeof pre);
        memset(suf,0,sizeof suf);
        int n;
        cin >> n;
        for(int i = 0;i<n;++i)
            cin >> a[i];

        pre[0] = a[0];
        suf[n-1] = a[n-1];
        for( int i = 1; i < n; ++i )
            pre[i] = gcd( pre[i-1], a[i] );
        for( int i = n-2; i >= 0; --i )
            suf[i] = gcd( suf[i+1], a[i] );

        int maxGcd = pre[n-1]; // 总要有个初始值吧 要不然没法比较对不对?  pre[n-1] == suf[0];
        for(int i = 0;i<n;++i)
        {
            if(i==0)
                maxGcd = max( maxGcd, suf[1] );
            else if(i==n-1)
                maxGcd = max( maxGcd, pre[n-2] );
            else
                maxGcd = max( maxGcd, gcd(pre[i-1],suf[i+1]) );
        }
        cout << maxGcd << endl;
    }
    return 0;
}

看不懂的地方请留言以让我改进,谢谢!

参考文章 https://www.cnblogs.com/heihuifei/p/7813713.html