HDU - 6025 Coprime Sequence（前缀gcd+后缀gcd）

题意：去除数列中的一个数字，使去除后数列中所有数字的gcd尽可能大。

分析：这个题所谓的Coprime Sequence，就是个例子而已嘛，题目中没有任何语句说明给定的数列所有数字gcd一定为1→_→，队友这样解读题目导致我们队的思路完全想歪了，当时真的脑子发懵，为啥没再读一遍题= =

1、求出一个数列的gcd跟计算顺序没关系。

2、如果求去掉下标为i的数字后整个数列的gcd，直接将该数字前的所有数字的gcd（prefix[i-1]）和该数字后所有数字的gcd(suffix[i+1])再求一下gcd就好了。

3、预处理前缀gcd和后缀gcd即可。

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 100000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int a[MAXN];

int prefix[MAXN];

int suffix[MAXN];

int gcd(int a, int b){

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

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        memset(prefix, 0, sizeof prefix);

        memset(suffix, 0, sizeof suffix);

        int n;

        scanf("%d", &n);

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

            scanf("%d", &a[i]);

        }

        prefix[0] = a[0];

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

            prefix[i] = gcd(prefix[i - 1], a[i]);

        }

        suffix[n - 1] = a[n - 1];

        for(int i = n - 2; i >= 0; --i){

            suffix[i] = gcd(suffix[i + 1], a[i]);

        }

        int ans = max(suffix[1], prefix[n - 2]);

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

            ans = max(ans, gcd(prefix[i - 1], suffix[i + 1]));

        }

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

    }

    return 0;

}

巴特西

HDU - 6025 Coprime Sequence（前缀gcd+后缀gcd）

最新文章

热门文章