HDU - 6025 Coprime Sequence 典型前缀后缀

本文主要是介绍HDU - 6025 Coprime Sequence 典型前缀后缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一个序列，任意去掉一个，问整个序列的最大公约数。
前缀和，后缀和思想
求前缀最大公约数，后缀最大公约数，然后找gcd（前缀gcd，后缀gcd）中最大的。
具体思想：开两个数组，第一个数组a保存前缀gcd，a[i]表示，从1到i的最大公约数。第二个数组b保存后缀gcd，b[i]表示，从n到i的最大公约数。
去掉第i个数的最大公约数为gcd(a[i-1],b[i+1]).over！

//提高cin的效率
std::ios::sync_with_stdio(false);

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll maxn = 100005;
int l[maxn],r[maxn],num[maxn];
int main(){std::ios::sync_with_stdio(false);int T;cin>>T;while(T--){int n;cin>>n;for(int i=0;i<n;i++) cin>>num[i];l[0] = num[0];r[n-1] = num[n-1];for(int i=1;i<n;i++)l[i] = __gcd(l[i-1],num[i]);for(int i=n-2;i>=0;i--)r[i] = __gcd(r[i+1],num[i]);int d = max(l[n-2],r[1]);for(int i=1;i<n-1;i++){d = max(d,__gcd(l[i-1],r[i+1]));}cout<<d<<endl;}return 0;
}

这篇关于HDU - 6025 Coprime Sequence 典型前缀后缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---