HDU6025 Coprime Sequence（gcd）

处理出数列的 \(gcd\) 前缀和后缀，删除一个数后的 \(gcd\) 为其前缀和后缀的 \(gcd\) 。

遍历数列取 \(max\) 即为答案。

时间复杂度为 \(O(n)\) 。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int a[maxn], head[maxn], tail[maxn];

int t, n;

int gcd(int a, int b)

{

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

}

int main()

{

    for(scanf("%d", &t); t--; ){

        scanf("%d", &n);

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

        head[0] = tail[n + 1] = 0;

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

        for(int i = n; i >= 1; i--) tail[i] = gcd(tail[i + 1], a[i]);

        int ans = 0;

        for(int i = 1; i <= n; i++){

            ans = max(ans, gcd(head[i - 1], tail[i + 1]));

        }

        cout << ans << endl;

    }

    return 0;

}

巴特西

HDU6025 Coprime Sequence（gcd）

最新文章

热门文章